Shortest path with a fixed number of edges

Find the shortest path through a graph in efficient time, with the additional constraint that the path must contain exactly n nodes.

We have a directed, weighted graph. It may, or may not contain a loop. We can easily find the shor开发者_高级运维test path using Dijkstra's algorithm, but Dijkstra's makes no guarantee about the number of edges.

The best we could come up with was to keep a list of the best n paths to a node, but this uses a huge amount of memory over vanilla Dijkstra's.

It is a simple dynamic programming algorithm.

Let us assume that we want to go from vertex x to vertex y.

Make a table D[.,.], where D[v,k] is the cost of the shortest path of length k from the starting vertex x to the vertex v.

Initially D[x,1] = 0. Set D[v,1] = infinity for all v != x.
For k=2 to n:
  D[v,k] = min_u D[u,k-1] + wt(u,v), where we assume that wt(u,v) is infinite for missing edges. 
  P[v,k] = the u that gave us the above minimum.

The length of the shortest path will then be stored in D[y,n].

If we have a graph with fewer edges (sparse graph), we can do this efficiently by only searching over the u that v is connected to. This can be done optimally with an array of adjacency lists.

To recover the shortest path:

Path = empty list
v = y
For k= n downto 1:
  Path.append(v)
  v = P[v,k]
Path.append(x)
Path.reverse()

The last node is y. The node before that is P[y,n]. We can keep following backwards, and we will eventually arrive at P[v,2] = x for some v.

The alternative that comes to my mind is a depth first search (as opposed to Dijkstra's breadth first search), modified as follows:

• stop "depth"-ing if the required vertex count is exceeded

• record the shortest found (thus far) path having the correct number of nodes.

Run time may be abysmal, but it should come up with the correct result while using a very reasonable amount of memory.

Interesting problem. Did you discuss using a heuristic graph search (such as A*), adding a penalty for going over or under the node count? This may or may not be admissible, but if it did work, it may be more efficient than keeping a list of all the potential paths.

In fact, you may be able to use backtracking to limit the amount of memory being used for the Dijkstra variation you discussed.

A rough idea of an algorithm:

Let A be the start node, and let S be a set of nodes (plus a path). The invariant is that at the end of step n, S will all nodes that are exactly n steps from A and the paths will be the shortest paths of that length. When n is 0, that set is {A (empty path)}. Given such a set at step n - 1, you get to step n by starting with an empty set S1 and

for each (node X, path P) in S
  for each edge E from X to Y in S, 
    If Y is not in S1, add (Y, P + Y) to S1
    If (Y, P1) is in S1, set the path to the shorter of P1 and P + Y

There are only n steps, and each step should take less than max(N, E), which makes the entire algorithm O(n^3) for a dense graph and O(n^2) for a sparse graph.

This algorith was taken from looking at Dijkstra's, although it is a different algorithm.

let say we want shortest distance from node x to y of k step simple dp solution would be

A[k][x][y] = min over { A[1][i][k] + A[t-1][k][y] } k varies from 0 to n-1

A[1][i][j] = r[i][j]; p[1][i][j]=j;
for(t=2; t<=n; t++)
for(i=0; i<n; i++) for(j=0; j<n; j++)
{
A[t][i][j]=BG; p[t][i][j]=-1;
for(k=0; k<n; k++) if(A[1][i][k]<BG && A[t-1][k][j]<BG)
if(A[1][i][k]+A[t-1][k][j] < A[t][i][j])
{
A[t][i][j] = A[1][i][k]+A[t-1][k][j];
p[t][i][j] = k;
}
}

trace back the path
void output(int a, int b, int t)
{
while(t)
{

cout<<a<<" ";
a = p[t][a][b];
t--;
}
cout<<b<<endl;
}