Shortest path with a fixed number of edges

2
votes

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 shortest 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.

5
algorithmpathdijkstra
This was an in-class example for Zhe Dang's Algorithms class, it was not assigned as homework. I just thought it was an interesting problem. – Phill
I don't think you can satisfy both "shortest path" and "a fixed number of edges" constraints. – Nick Dandoulakis
It think it means that "of the paths that contain exactly n nodes, find the shortest". Note that there may not be an answer (e.g. all paths take more than n nodes). – Kathy Van Stone
Nick D - read the problem as "Given the paths that have n edges, which of these has the shortest path?" It's certainly satisfiable - he's just wanting an efficient way to find it. – James Kolpack
If "the path must contain exactly n nodes", then the "shortest path" will be exactly n nodes long. The way this is worded, all you have to do is find ANY path consisting of n nodes. – mbeckish

5 Answers

7
votes

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.

0
votes

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.

0
votes

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.

0
votes

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.

-1
votes

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;
}