The undirected two disjoint shortest paths problem

The k disjoint shortest paths problem (k-DSPP) on a graph with k source–sink pairs (si,ti) asks if there exist k pairwise edge- or vertex-disjoint shortest si–ti-paths. It is known to be NP-complete if k is part of the input. Restricting to 2-DSPP with strictly positive lengths, it becomes solvable in polynomial time. We extend this result by allowing zero edge lengths and give a polynomial-time algorithm based on dynamic programming for 2-DSPP on undirected graphs with non-negative edge lengths.     «

The k disjoint shortest paths problem (k-DSPP) on a graph with k source–sink pairs (si,ti) asks if there exist k pairwise edge- or vertex-disjoint shortest si–ti-paths. It is known to be NP-complete if k is part of the input. Restricting to 2-DSPP with strictly positive lengths, it becomes solvable in polynomial time. We extend this result by allowing zero edge lengths and give a polynomial-time algorithm based on dynamic programming for 2-DSPP on undirected graphs with non-negative edge lengt...     »