访问k个顶点的无向图中的最短路径
考虑一个无向图。 有n个顶点和m个边。 所有的边都有一个与之相关的重量。
我想设置一个算法，它将采用一个源顶点's'，一个sink顶点't'和一个数字'k'作为输入。 算法的输出是从s到t之间具有k个顶点的最短路径。
请建议。 谢谢！
创建与您的图形关联的[numvertices] [numvertices]的距离矩阵。 然后运行Floyd算法，但只是k次迭代而不是numvertices迭代。
经过小范围的研究，我发现这个问题是NP-Hard。 因此我必须使用参数化技术来解决这个问题。 我用过的算法是一个固定参数可处理的算法。
我在算法中使用了Lawler对日元算法的修改来解决这个问题。 Yen的算法有助于找出无环路网络中前n条最短路径。 以下是我的算法：
从用户获取参数k（路径中的顶点数）。 同样从用户那里得到'm'，这是路径不应超过的最大距离。 这是将帮助我们在多项式时间内解决NP-Hard问题的参数。
这一步使用Yen的算法。 找到下一个最短路径。 检查路径是否有k个顶点。
一个。 如果是，则中止并返回路径b。 否则，2
如果路径的总距离超过参数'm'，则中止并返回'无结果'
Yen的算法使用Dijkstra算法找到最短路径。 实现这个算法解决这个问题很有趣。
链接地址: http://www.djcxy.com/p/35295.html上一篇: Shortest path in an undirected graph that visits k vertices