Finding a shortest path that passes through some arbitrary sequence of nodes?

Question

In this earlier question the OP asked how to find a shortest path in a graph that goes from u to v and also passes through some node w. The accepted answer, which is quite good, was to run Dijkstra's algorithm twice - once to get from u to w and once to get from w to v. This has time complexity equal to two calls to Dijkstra's algorithm, which is O(m + n log n).

Now consider a related question - you are given a sequence of nodes u₁, u₂, ..., u_k and want to find the shortest path from u₁ to u_k such that the path passes through u₁, u₂, ..., u_k in order. Clearly this could be done by running k-1 instances of Dijkstra's algorithm, one for each pair of adjacent vertices, then concatenating the shortest paths together. This takes time O(km + k n log n). Alternatively, you could use an all-pairs shortest paths algorithm like Johnson's algorithm to compute all shortest paths, then concatenate the appropriate shortest paths together in O(mn + n² log n) time, which is good for k much larger than n.

My question is whether there is an algorithm for solving this problem that is faster than the above approaches when k is small. Does such an algorithm exist? Or is iterated Dijkstra's as good as it gets?

Answer 1

Rather than running isolated instances of Dijkstra's algorithm to find the paths u(k) -> u(k+1) one path at a time, can a single instance of a modified Dijkstra-like search be started at each node in the sequence simultaneously, with the paths formed when search regions meet "in-the-middle".

This would potentially cut down on the total number of edges visited and reduce re-traversal of edges compared to making a series of isolated calls to Dijkstra's algorithm.

An easy example would be finding the path between two nodes. It would be better to expand the search regions about both nodes than just expanding about one. In the case of a uniform graph, the second option would give a search region with radius equal to the distance between the nodes, the first option would give two regions of half the radius - less overall search area.

Just a thought.

EDIT: I guess I'm talking about a multi-directional variant of a bi-directional search, with as many directions as there are nodes in the sequence {u(1), u(2), ..., u(m)}.