graph traversal - finding 2 shortest paths for 2 entities such they are never in contact (both at the same node)

Question

I'm trying to figure out something like this.

In a graph, there are 2 start nodes and 2 destination nodes. Find the optimal paths from the 1st start to the 1st destination, and the other start to the other destination, such that if two entities were to travel along these paths, they would never be at the same node.

My first thought (although I really have no idea) would be to use any shortest path algorithm, let's say Dijkstra's. Run the algorithm once for the first entity, and store the node chosen for every step in an array. Run the algorithm a second time for the second entity, and if the chosen node for a step is the same as it was for the first entity at that array index, then they would collide, so choose the next best node instead. There must be a better way to do this.

Could use some suggestions. Thanks!

Answer 1

I think you might consider a dynamic programming approach. At iteration 0, let s_0 = {(origin_0, origin_1)}. For iteration k+1, let s_k+1 = {(x,y) | x != y, exists an (prev_x, prev_y) in s_k s.t. e(prev_x, x) in E and e(prev_y, y) in E}. This should proceed forward with |s| < V^2 for every s. So if the best case distance is d, you should be able to do this in d*V^2 time. Good luck on doing better!

Update: The above solution actually runs in d * E^2, as per the comments below. Note that it will converge within d = V^2 iterations, so the total time is (VE)^2. But more importantly, this algorithm is actually the same as just running Bellman Ford on the product graph G' = (V', E') where V' = {(x,y) | x <- V, y <- V, x != y} and two nodes u = (x,y), v = (x',y') in V' share an edge if there is an edge e(x,x') and e(y,y') in the original edge set E. But now that we've defined our algorithm as Bellman Ford on the product graph, we might as well run Dijkstra's Algorithm! Note that the order of G' (number of vertices) is V^2 - V = O(V^2), and the number of edges in G' is O(E^2). Thus, running Dijkstra's using a Fibbonacci heap will take us at most O(E^2 + V^2 log V), which for anything other than the sparsest of graphs will essentially be O(E^2)! That's a major improvement. If you actually want to run this, you can use a graph library to build the product graph, and then just call shortest paths from (x0, y0) to (xT, yT).

The memory cost of this algorithm is O(E^2) because that's what it takes to explicitly form the product graph. You really don't need to do that though - Dijkstra's only needs to keep the vertices min cost in memory, and you could generate the edges on the fly to keep that down to O(V^2) memory. The code will be a lot uglier though, as you may have to roll Dijkstra's yourself. Also, if you're operating on a really big graph that you couldn't possible precompute the product of, you might consider running iterative deepening (http://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search) on the product graph. If this problem is actually important for a real world use case of yours, feel free to ask more.

Answer 2

Here's what should be a quicker way. As above, run the two queries in parallel, but store two costs for each arc, one for each query. Initially both costs are the same for all arcs. When a query step reaches a node, set the costs for the other query, for all incoming arcs of that node, to infinity.