Re: n edges shortest path

Michal Brzozowski wrote:
> samipate@xxxxxxxxx wrote in message
news:<1114550264.734142.128090@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>...
> > Hello list
> >
> > Is there a well known algorithm that determines in an oriented
graph
> > the shortest path using exactly n edges ?
>
> hello
>
> One algorithm I can think of would be adding another axis to
> the vertices, so instead of 1..k they would be:
> (1,1) ... (k,1)
> (1,2) ... (k,2)
> .
> .
> .
> (1,n) ... (k,n)
>
> the second number in the pair would of course represent the number of
edges
> that you took to given vertex.

You forgot to specify the edges and weights of this graph. In the above
notation, (x,i) should be adjacent to (y,j) iff (1) x is adjacent to y
and (2) j = i+1. If (x,i) is adjacent to (y,j) then let the weight of
the edge equal the weight of the edge joining x to y.

Let s denote the source vertex. In the "associated graph", the length
of the shortest path from (s,0) to (x,i) corresponds to the length of
the shortest i-edge path from s to x. This is most easily proven in two
steps. First, show that there exists a path from (s,0) to (x,i) in the
associated graph iff there exists an i-edge path from s to x in the
original graph. Second, show that the length of any path from (s,0) to
(x,i) equals the length of the corresponding path in the original
graph.

If V and E are the vertex and edge sets of the original graph then the
associated graph has O(n*|V|) vertices and O(n*|E|) edges. If the
problem is solved using Dijkstra's algorithm you thus get a worst-case
runtime of O(n*(|V|+|E|)*log(|V|)). In other words, O(n) times more
work than the standard shortest path problem for the graph.

Another option is to use a dynamic programming algorithm. If d(x,i) is
the length of the shortest i-edge path from s to x then we have the
recurrence relations:

d(s,0) = 0
d(x,0) = infinity for any x != s
d(x,i+1) = min(y is adjacent to x){d(y,i) + w(x,y)}

(Here w(x,y) is the weight of the edge joining x and y.)

These relations give rise to a really simple dynamic programming
algorithm with a runtime complexity of O(n*u*|V|) where u is the
maximum outdegree of any vertex in the graph.

Per

.

Relevant Pages

  • Re: Shortish paths
    ... original graph. ... The functionality of Dijkstra's original algorithm can be extended ... optimal solution is removed from the graph, ... I intend to begin by rereading the shortest path sections of Cormen ...
    (comp.theory)
  • Re: Shortish paths
    ... Remember I'm not asking for an algorithm, just for advice on what to ... original graph. ... optimal solution is removed from the graph, ... I intend to begin by rereading the shortest path sections of Cormen ...
    (comp.theory)
  • Re: Graph optimization
    ... represented in the form of a graph. ... I have to add up all the weights to form the ... algorithm is going to be the best for finding the shortest path ...
    (comp.programming)
  • Re: Graph Algorithm Question
    ... is there an algorithm to do the following: ... However the graph should contain no directed ... cycle whose weight is negative. ... If all the edges weighs are positive then shortest path from X to X is ...
    (comp.theory)
  • Re: Shortish paths
    ... For how many nodes and how many edges will the actual algorithm run ... original graph. ... optimal solution is removed from the graph, ... I intend to begin by rereading the shortest path sections of Cormen ...
    (comp.theory)