Finding a shortest path that passes through some a

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

Looking at your problem from a divide-and-conquer perspective, given graph G with n nodes, k of which [1<=k<=n] we want to traverse in order from 1-k (i1,i2,...,ik),

Let's say f(j) is the shortest path from i1 to ij. The problem nicely subdivides (you already see where this is going) into smaller instances of finding shortest paths, eventually turning into summation of f(j) as j goes from 1 to k. Therefore, your problem is minimum bounded by k-1 iterations of Djikstra's algorithm. The only way to improve it would be to find a faster algorithm than Djikstra's to discover the shortest path between 2 points.

At least that's my take on it. /grad student

Answer 2

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)}.

Answer 3

You get the shortest path from one vertex to all the other in the graph by one call to Dijkstra's algorithm. Thus you only need to do a search for each unique starting vertex so repeated vertices does not make the problem any harder.

Answer 4

I don't see how we can do too much better, here's all I can think of. Assuming the graph is undirected, the shortest path from any node u to node v would be the same as that from v to u (in reverse of course).

Now, for your case of a shortest path in the order u1 u2 u3.. un, we could run Djikstra's algorithm on u2 (and find the shortest paths u1-u2, u2-u3 in one run), then on u4 (for u3-u4 and u4-u5), then u6.. and so on. This reduces the number of times you apply Djikstra's by roughly a half. Note that complexity wise, this is identical to the original solution.