[Math] Shortest path between nodes in a graph with multiple sources and destinations? (No collisions.)

Question

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!

Answer 1

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.