最短路径不是图中的路径
我想知道是否有一种算法可以找到图中的最短路径。
假设我有一张图，其中有几条从一个顶点到另一个顶点的路径。这些路径中的两个或多个具有相同的成本。我如何标记、查找等这些顶点之间的所有最短路径？据我所知，Dijkstra 或 Bellman-Ford 算法会找到最短路径，但它们只“选择”一条。
I was wondering if there is an algorithm which would find shortest paths in graph.
Let's say that I have a graph where there are couples of path from one vertex to another. Two or more of these paths have the same cost. How can I mark, find etc all shortest paths between these vertices ? As far as I know Dijkstra or Bellman-Ford algorithms will find shortest path but they "choose" only one.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
Dijkstra 算法给出了所有可能的中间节点的成本，以及到达接收器的最短路径的成本。您可以通过从接收器到源（向后）进行深度优先搜索来获取从源到接收器的所有路径，其中仅当该边的成本等于从源到两个节点的最短路径。当然，您会以相反的顺序获得路径，但反转它们很容易。
。
Dijkstra's algorithm gives you the cost to all the possible intermediate nodes, and the cost of the shortest path to the sink. You can get all the paths from source to sink by doing a depth first search from the sink to the source (going backwards), where you traverse an edge (backwards) only if the cost of that edge is equal to the difference between cost of the shortest path from the source to the two nodes. Of course you get the paths in reverse order, but reversing them is easy.
.
看看Floyd-Warshall。
Take a look at Floyd-Warshall.