























The $k$ disjoint shortest paths problem ($k$-DSPP) on a graph with $k$ source-sink pairs $(s_i, t_i)$ asks for the existence of $k$ pairwise edge- or vertex-disjoint shortest $s_i$-$t_i$-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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。