Thursday, September 10, 2015

Shortest path and back

This Stack Overflow question reminded me of a very interesting problem, whose solution is difficult to find online (in fact I can no longer find it mentioned, though I might be forgetting the exact terminology).

The problem is this:

Given a graph, find the shortest path from a source s to a destination d and back to s. We will call this the shortest path and back problem, or the shortest round trip problem.

A naive algorithm is to simply use Dijkstra's algorithm, or any shortest path algorithm, to find a shortest path from s to t, remove its edges from the graph, then find a return path in the new graph. We can easily find examples for which this fails though.

The correct algorithm involves solving the minimum cost maximum flow problem. This is solved quite easily with the Edmonds-Karp algorithm, where the Breadth-First search used to find the shortest augmenting paths at each step is replaced with the Bellman-Ford algorithm.

I'll leave the details as an exercise, but give an algorithm that is easier to understand if you're not too familiar with flow networks. You can use this algorithm to figure out the flow solution, since the two are actually equivalent.

It goes like this (also available on the SO link):

  • Find a shortest path s -> d with any algorithm that can do this (Dijkstra if no negative costs, Bellman-Ford otherwise);
  • Replace the edges of this shortest path with directed arcs directed from towards s. For example, if your shortest path is s -> x -> y -> z -> d, replace the edge (s, x) with the directed arc x -> s(x, y) with the directed arc y -> x etc.
    Also negate the costs of these arcs. For example, if 
    (x, y) had cost c, the directed arc y -> x will have cost -c;
  • Find a shortest path from s to d in this new graph. You'll have to use an algorithm that works with negative edges now;
  • Remove the edges that appear in both of the shortest paths. What you're left with is the cycle you're after.

  • As an example, consider the following graph. 

    The first shortest we find is 1 -> 2 -> 3 -> 4, of cost 12. We transform our graph to:

    Notice the negated costs. We then find another shortest path in this new graph, which can only be 1 -> 3 -> 2 -> 4, of cost 14.

    We have used the edge (2, 3) in both shortest paths, so we ignore it and draw our solution shortest path and back:

    Which has total cost 26. Notice that if we had applied the naive algorithm, we would have selected 1 -> 4 as the second path, which would have led to a cost of 28.

    You can also solve this problem on UVA, where you can practice your implementation of the algorithm.

    No comments:

    Post a Comment

    Keep it technical and related to the subject matter. Personal comments of any kind will be deleted.