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$
  • 1
    $\begingroup$ Optimal ... means least sum edge weights of both paths? $\endgroup$ – DanielV Jan 13 '19 at 17:15
1
$\begingroup$

This is called the node disjoint shortest paths problem. This paper shows that several variants are NP-complete for more than two source-sink pairs.

| cite | improve this answer | |
$\endgroup$
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$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ How do we know we don't run into a local minimum without exhaustively checking every combination of S1D1, S2D2, ..., SNDN? $\endgroup$ – user1952534 Nov 24 '19 at 21:17
0
$\begingroup$

One possible phrasing of the problem would be as minimum-cost-flow-problem.

It's a generalization of network flow, in which the edges each have a price that has to be paid if flow wants to flow through them.

You'd pick the capacity of all edges to be 1, and model the cost of each edge as the edge-weight in your original problem.

Finally, you replace every node $t$ by the construct $t_{in}\to t_{out}$,i.e. by two connected nodes, giving the edge between them capacity 1 and cost 0.

However, as another answer says this problem is NP-hard, the output flow might not be legitimate (though I can't say where exactly it might go wrong).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This model would not prevent flow for different source-sink pairs from sharing an edge, say with $1/2$ flow each. I think you would need a separate commodity for each source-sink pair, and you would also need to enforce integrality, so you would have an integer multicommodity flow problem. $\endgroup$ – RobPratt Jan 19 at 1:40
  • $\begingroup$ @RobPratt Isn't the generalized version of the augmenting path algorithmus guaranteed to always return an integer flow if all capacities are integers? $\endgroup$ – Sudix Jan 19 at 16:25
  • 1
    $\begingroup$ I guess the real issue with using only a single commodity is not fractionality but rather that you might get a path from s1 to d2 and a path from s2 to d1. If you introduce multiple commodities, then integrality is not guaranteed without explicitly imposing it. $\endgroup$ – RobPratt Jan 19 at 20:45

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.