c# - 在图中找到一对节点之间的 K 最短路径？

Question

有谁知道寻找k-最短路径的算法，我在网上搜索并找到了Yen's，但它是如此复杂？

非常感谢。

score 3 · Accepted Answer

它不能有效地完成（多项式）¹ - 问题是NP-Hard

这样想 - 你是否可以多项式地找到 ak 最短路径的长度（假设这里是简单路径），通过对的范围[1,n!]进行二进制搜索k，你可以找到图中是否存在哈密顿路径（通过查找一条长度的路径n）。

由于哈密顿路径问题是 NP-Hard，所以这个问题也是如此，并且没有已知的多项式解决方案。

(1) 可能，除非P=NP，但大多数 CS 研究人员认为这不太可能

score 1 · Accepted Answer

1

现在总...

谷歌搜索 Djikstra 算法。这里有一个实现。

于 2013-01-21T08:30:11.853 回答

score 0 · Accepted Answer

这是通过不相交集解决的。谷歌它，但简而言之，你有 2 个向量。一个用-1初始化的父母。另一个用零初始化的等级。现在从源节点开始。你去寻找你可以从那里得到的每个可能的节点。通过使它们的 parent[i] = 当前节点将它们添加到您的集合中。根据持有数字的 rank[i] 决定谁是谁的父母

3 回答 3