c# - 使用Dijkstras寻找 "k"最短路径

Question

我已经可以使用 Dijkstra 算法找到两个顶点之间的最短路线:wiki Dijkstra's .

但是。我的一些边缘旨在用作“检查点”，因为您必须至少通过一个检查点才能获得可用的路线。

有时，算法会找到一条不包含这些边检查点的路径。在那种情况下，我想找到第二个。最短路线 - 如果该路线也不包含检查点，则找到第三条路线。最短路线等。

有什么让我开始的想法吗？

编辑:

是否可以在第一条路线上遍历所有前驱，然后从前驱到目的地运行Dijkstras(并排除原先选择前驱的下一个goto顶点)。这样我就有可能找到所有可能的路线，然后将它们相互比较？

例子。

A = 来源Z = 目的地

最短路径:A -> B -> C -> D -> Z

第二。最短路径:A -> B -> C -> D -> “成本最低的顶点，不是 Z”(如果在当前尝试中找不到可用路径，则循环遍历 D 的所有未访问邻居)

如果第二。最短路径也不包含检查点，尝试第三短

第三。最短路径:A -> B -> C -> 成本最低的顶点，不是 D

或者这个解决方案无论如何都不可能？

编辑 2:

可能很难看清，但紫色的 1x3 像素是顶点。黄色道路是边缘，粉色 3x3 像素也是。粉红色的也是所谓的检查站。所以我必须找到最短路线并至少通过一个检查站。

Answer 1

您可以通过多种方式尝试完成这项工作。

我们称 S 为起始节点，D 为目标节点，I 为中间节点。

[单中间节点]一个简单但次优的解决方案是使用 Dijkstra 从 S 到 I，然后将 Dijkstra 的结果从 I 附加到 D。

[多个中间节点]正如 Niklas B. 指出的，一种可行的方法是“从 S 和 D 构建最短路径树。对于每个中间节点 A，检查 d(S, A) + d(T, A)。最小值是解决方案。运行时间是 Dijkstra 的两倍，例如 O((n+m) log n) with binary heaps”。