graph - 访问k个顶点的无向图中的最短路径

Question

考虑一个无向图。有n个顶点和m个边。所有的边都有一个与之相关的权重。

我想设计一种算法，它将源顶点“s”、汇顶点“t”和数字“k”作为输入。该算法的输出是从 s 到 t 的最短路径，在 s 和 t 之间有 k 个顶点。

请建议。谢谢！

Answer 1

经过一个小的研究，我发现这个问题是 NP-Hard。因此我不得不使用参数化技术来解决这个问题。我使用的算法是一个固定参数易处理的算法。

我在我的算法中使用了Lawler对日元算法的修改来解决这个问题。Yen 的算法有助于找出无环网络中的前 n 条最短路径。这是我的算法的运行方式：

1. 从用户那里获取参数k（路径中的顶点数）。还要从用户那里得到“m”，这是路径不应超过的最大距离。这是将帮助我们在多项式时间内解决 NP-Hard 问题的参数。

2. 这一步使用日元算法。找到下一条最短路径。检查路径是否有 k 个顶点。

   一个。如果是，则中止并返回路径 b。否则，2

3. 如果路径的总距离超过参数'm'，则中止并返回'no result'

Yen 算法使用 Dijkstra 算法来寻找最短路径。实现这个算法来解决这个问题很有趣。

Answer 2

创建与您的图形关联的 [numvertices][numvertices] 距离矩阵。然后运行 ​​Floyd 算法，但只是 k 次迭代而不是 numvertices 次迭代。