Abstract: | The disjoint shortest paths problem (-DSPP) on a graph with source–sink pairs asks if there exist pairwise edge- or vertex-disjoint shortest –-paths. It is known to be NP-complete if is part of the input. Restricting to -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 -DSPP on undirected graphs with non-negative edge lengths. |