algorithm - K-first 短路径算法的搜索

Question

我发现许多算法和方法都在谈论寻找最短路径或问题的最佳/最佳解决方案。但是，我想做的是一种算法，它可以找到从一个点到另一个点的第一条 K 最短路径。我面临的问题更像是在树中搜索，当您采取的每一步都有多个选项时，每个选项都有其权重。什么样的算法用于面对这类问题？

Answer 1

Jose Santos在2006 年的论文中比较了三种不同的 K 最短路径查找算法。

Answer 2

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

更简单的算法和讨论： 关于无向图的 KSPA 建议

Answer 3

编辑：显然我点击了一个链接，因为我以为我在回答一个新问题；如果 - 很可能 - 这个问题对你来说不再重要，请忽略这个。

---

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

---

如果您的实际意思是修复源并获取k与该源距离最小的节点，那么一个 BFS 就可以了。如果您的意思是同时修复源和目标，那么一个 BFS 也足够了。

---

我不明白如何在不了解树结构的情况下使用从节点到下一级节点的所有边具有相同权重的事实。