Shortest path between nodes in a graph with multiple sources and destinations? (No collisions.) 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: 


*

*Is it possible to solve this with a fast algorithm? Or at least... 

*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! 
 A: 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.
A: 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$.
A: 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).
