搜索K-first短路径算法

Question

我发现了许多算法和方法，这些算法和方法讨论寻找最短路径或问题的最佳/最优解决方案。但是，我想要做的是找到从一个点到另一个点的第一个K最短路径的算法。我面临的问题更像是通过树进行搜索，在每一步中，每个步骤都有多个选项。使用哪种算法来面对这类问题？

Answer 1

There is the 2006 paper by Jose Santos 比较三种不同的K-最短寻路算法。

Answer 2

日元的算法实现： http://code.google.com/p/k-shortest-paths/

更简单的算法&讨论： Suggestions for KSPA on undirected graph

Answer 3

编辑：显然我点击了一个链接，因为我觉得我是在回答到一个新的问题;如果 - 很可能 - 忽略这个问题 - 这个问题对你来说并不重要。

---

鉴于您正在处理的问题的限制版本，这变得更容易实现。需要注意的最重要的事情是，在树中，最短路径是两个节点之间的唯一路径。所以你要做的就是解决所有对最短路径，即树中的O(n²)做n BFS遍历，然后你得到最小值k。这可能可以通过某种方式进行优化，但这种做法的天真方法是对O(n² log n)时间的O(n²)距离进行排序，并将k的最小值进行排序;通过一些记录，您可以跟踪哪个距离对应于哪条路径，而无需时间复杂性开销。这会比使用KSPA算法的O(n²)可能的s-t对更好的复杂性。

---

如果你实际上意味着是固定源，并得到与来自该源的最小距离的k节点，一个BFS会做。如果你的意思是固定源和目标，那么一个BFS就足够了。

---

我不看你如何使用的事实，下面从节点去节点的水平边缘都具有相同的权重不知道更多关于树的结构。