Hi,

I want to find a lowest path, with length of N, from a vertex s in a
directed edge-weighted graph G. Each vertex has M inputs edge and M leaving
edges. The problem is the weight of edge (x_i,x_(i+1)) is decided by the
input edge (x_(i-1), x_i) and the following edge (x_(i+1),x_(i+2)).
  Do you have any idea about this kind of problems?

Cheers

Fishman

"Fishhman" <s012006@cuhk.edu.hk> wrote:


> I want to find a lowest path, with length of N, from a vertex s in a
> directed edge-weighted graph G. Each vertex has M inputs edge and M leaving
> edges. The problem is the weight of edge (x_i,x_(i+1)) is decided by the
> input edge (x_(i-1), x_i) and the following edge (x_(i+1),x_(i+2)).

That isn't well defined yet, since from your description, for any edge, it
has an ambiguity among M predecessor edges and M successor edges.  Please
explain more clearly.

xanthian.

xanthian@well.com (Kent Paul Dolan) wrote in message news:<a3eaa964.0306272057.22d83be4@posting.google.com>...
> "Fishhman" <s012006@cuhk.edu.hk> wrote:
> 
> 
> > I want to find a lowest path, with length of N, from a vertex s in a
> > directed edge-weighted graph G. Each vertex has M inputs edge and M leaving
> > edges. The problem is the weight of edge (x_i,x_(i+1)) is decided by the
> > input edge (x_(i-1), x_i) and the following edge (x_(i+1),x_(i+2)).
> 
> That isn't well defined yet, since from your description, for any edge, it
> has an ambiguity among M predecessor edges and M successor edges.  Please
> explain more clearly.
> 
> xanthian.

A example of my problem is in a tree containing four layers, the first
layer has one node. This node has M children making up of the second
layer. Each edge, between the parent and one of its childs, has a
weight. All these four layers are constructed by above way. Each edge
has a constant weight except for the edges between the second and
third layers. The weights of those special edges are decided by the
search process. They are functions of the selection of the above edge
from the first layer to the second layer and the below edge between
the third layer and the fourth.
  I'd like to search a path from the first layer to the fourth layer.
This path should contain the lowest weight.
  Is it clearer? Thank you.

Fishman