论文标题
部分不连接k最短路径
Partially Disjoint k Shortest Paths
论文作者
论文摘要
$ k $最短路径问题的解决方案可能会输出与单个边缘相同的路径。另一方面，$ k $独立最短路径问题的解决方案由既不共享边缘也不具有中间节点的路径组成。我们调查了输出$ k $ -set中任何两个路径之间未共享边缘数量的情况。我们研究了两个主要方向：探索\ emph {近短}路径并探索\ emph {恰好最短路径}。我们假设加权图$ g =（v，e，w）$没有平行边缘，边缘长度（权重）为正。我们的结果也被推广到$ k $最短路径的情况下，在每个边缘有几个权重，结果应考虑到多标准优先权重。
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.
