3
$\begingroup$

Dijkstra's algorithm is a well-known method for finding the shortest path between two nodes in a graph. For instance, let's say that we have a graph like this:

base graph

Imagine that we want to get from the first source (S1) to the first destination (D1) with the shortest possible path. A simple application of Dijkstra's algorithm would yield this result:

dijkstra's simple

But let's say that we want to also connect the second source (S2) to the second destination (D2) without using any nodes or edges used by the first path. Naively applying Dijkstra's algorithm to the remaining available nodes and edges in the graph yields this result:

djikstra's problem

This is clearly sub-optimal! If the first path had been less greedy and taken the worse path, it could have made room for the second path to avoid an even worse path:

optimized

I've been scouring the internet for algorithms buried somewhere in graph theory that might address this problem. I would really like to know:

  1. Is it possible to solve this with a fast algorithm? Or at least...
  2. Can it be formulated as a linear programming problem?

This is a real-world computer programming problem. Even if it turns out to be NP-hard, partial solutions and heuristics are still extremely valuable.

Additionally, what I am actually trying to minimize here is the number of hops between nodes in a given graph, but that can easily be simulated by treating each edge as cost of 1—however, given two solutions that use an equal number of edges, the one with the lower total actual distance will be preferred.

Thanks to all!

$\endgroup$
  • $\begingroup$ Optimal ... means least sum edge weights of both paths? $\endgroup$ – DanielV Jan 13 at 17:15
0
$\begingroup$

A quick search didn't find any algorithms specifically for what you want. However, here's one (probably suboptimal) one that will solve your problem, with some likelihood.

Step 1: Pick $k$. (maybe $k\approx \sqrt{|V|}$? maybe $k\approx \ln |V|$?)

Step 2: Run the k-shortest-path algorithm of your choice, from S1 to D1. This can be done in $O(|E|+|V|\ln |V|+k)$ time. Store the results (a) by decreasing total path weight, (b) with the vertices in each path stored in both a list and a hash table.

Step 3: Repeat from S2 to D2.

Step 4: Pick a pair of paths (one from S1 to D1, one from S2 to D2), of smallest combined path weight. Test for collisions between the two paths, which can be done quickly using the hash table. (use the list of path 1, and for each, look up in the hash table of path 2). If no collision, done! If collision, pick the next pair of paths (by total weight). This can be done in $O(k^2m)$ time, where $m$ is the length (not weight) of the longest path from S1 to D1.

If your $k$ was too small, every pair of paths will intersect. Then, go back to step 1 and increase $k$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.