第 K 最短路径
有谁知道如何编写一个编程图算法（C++ 代码会很棒）来找到循环图中给定的一组节点和边的 Kth 最短路径？
例如，最短路径（可以由 Dijkstra 或 Bellman Ford 找到）被认为是第一条最短路径。现在，第二条最短路径是第一条最短路径之后的最短路径。现在我想让算法找到第 K 个最短路径。 给定节点数、边数和边集，如下所示：
节点数：5
边数：6
边缘：
0 1
0 2
1 2
2 3
3 1
1 4
源节点：0
目标节点：4
“请注意，该图包含一个循环” 谢谢。
Does anyone know how can I write a programming graph-algorithm (C++ code would be great) that finds the Kth shortest path for a given set of nodes and edges in a cyclic graph?
For example, the shortest path (that could be found by Dijkstra or Bellman Ford) is considered to be the 1th shortest path. Now the 2nd shortest path is the shortest one that comes after the 1st shortest path. Now I want the algorithm to find the Kth shortest path.
you are given the number of nodes, edges and the set of edges, as the following:
number of nodes: 5
number of edges: 6
edges:
0 1
0 2
1 2
2 3
3 1
1 4
source node:0
destination node: 4
"Note that this graph contains a cycle"
Thank you.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
使用统一成本搜索算法。如果维基百科说“返回解决方案”，请不要退出并
返回，而是将结果附加到某个列表，直到该列表包含k条路径。列表中的第 k 个元素（从 1 开始计数）将是第 k 个最短路径。不要保留“封闭”/“探索”集，否则该算法将无法正常工作。
Use a uniform cost search algorithm. Where the Wikipedia says "return solution", don't quit and
returnbut append the result to some list until that list contains k paths. The k'th element of the list (counting from 1) will be the k'th shortest path.Don't keep a "closed"/"explored" set or this algorithm won't work properly.