A solution of the $k$ shortest paths problem may output paths that are identical up to a single edge. On the other hand, a solution of the $k$ independent shortest paths problem consists of paths that share neither an edge nor an intermediate node. We investigate the case in which the number of edges that are not shared among any two paths in the output $k$-set is a parameter. We study two main directions: exploring \emph{near-shortest} paths and exploring \emph{exactly shortest paths}. We assume that the weighted graph $G=(V,E,w)$ has no parallel edges and that the edge lengths (weights) are positive. Our results are also generalized to the cases of $k$ shortest paths where there are several weights per edge, and the results should take into account the multi-criteria prioritized weight.
翻译：$k$ 最短路径问题的一个解决方案可能会输出与单一边缘相同的路径。 另一方面, $k$独立最短路径问题的一个解决方案包含一个不共享边缘或中间节点的路径。 我们调查输出 $k$ 设置 中任何两个路径之间没有共享的边缘数是一个参数的情况。 我们研究两个主要方向: 探索 emph{ ear- shorest} 路径和探索 emph{ exactly front room} 。 我们假设加权图形 $G=( V, E,w) 不存在平行边缘, 边长( 重量) 是正的。 我们的结果还被概括到每个边缘有多个重量的 $k$ 最短路径, 结果应该考虑到多标准优先的重量 。
相关内容
微信扫码咨询专知VIP会员