Shortest path with a fixed number of edges

Question

We were discussing this problem in class, and were unable to come up with a solution I found satisfying.

The problem: 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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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 cheapest path of length k from the root 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 cost of the cheapest path will then be stored in D[y,n].

If we have a graph with fewer edges, 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 cheapest 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.