搜索K-first短路径算法

Jose Santos撰写了2006年的论文  比较三种不同的K-最短路径寻找算法。     

Yen的算法实现： http://code.google.com/p/k-shortest-paths/ 更简单的算法＆amp;讨论： 关于无向图的KSPA建议     

编辑：显然我点击了一个链接，因为我以为我正在回答一个新问题;如果 - 很可能 - 忽略这一点 - 这个问题对你来说并不重要。 鉴于您正在处理的问题的受限制版本，实现起来要简单得多。最值得注意的是，在树中，最短路径是两个节点之间的唯一路径。所以你要做的就是通过做

n

BFS遍历解决所有对最短路径，即树中的

O(n²)

，然后得到

k

最小值。这可能会以某种方式进行优化，但是这样做的天真方法是在

O(n² log n)

时间内对

O(n²)

距离进行排序并取

k

最小值;通过一些簿记，您可以跟踪哪个距离对应于哪个路径而没有时间复杂度开销。这将比使用KSPA算法为

O(n²)

可能的s-t对提供更好的复杂性。 如果您实际意味着修复一个源并获得与该源距离最小的

k

节点，那么一个BFS就可以。如果你意味着修复源和目标，一个BFS就足够了。 我不知道如何使用这样一个事实，即从节点到下面级别的节点的所有边都具有相同的权重而不了解更多关于树的结构。