1

我对调整 Suurballe 的算法以找到从源到目的地的最佳 K 条路径而不是最好的两条路径很感兴趣。我认为人们一直都在这样做，但我一直在寻找几个小时，但找不到能清楚解释它的论文。在 Suurballe 的维基百科页面上有一篇关于它的论文的引用，但它没有详细说明前两个之后的扩展（如何修改图表和合并结果等）。顺便说一句，我实际上正在研究顶点不相交问题，而不是维基百科上阐明的边缘不相交问题。

我的简洁问题：您如何将 Suurballe 的算法扩展到两条路径之外？

4

2 回答 2

1

在文献中，这被称为连续最短路径问题，它的工作方式基本相同，只是重复。您修改每个已发现路径的权重的方式与修改第一个路径的方式相同。

于 2013-08-20T00:14:24.273 回答
0

Suurballe 算法用于寻找总长度最小的两条边不相交的路径。Suurballe 算法不能扩展到两个以上的边缘。

k-最短路径问题是一个不同的问题。这里最短的路径是

于 2020-11-26T14:24:52.277 回答