我想知道是否有一种算法可以在图中找到最短路径。
假设我有一张图，其中有几条从一个顶点到另一个顶点的路径。这些路径中的两条或多条具有相同的成本。如何标记、查找等这些顶点之间的所有最短路径？据我所知，Dijkstra 或 Bellman-Ford 算法会找到最短路径，但它们只会“选择”一条路径。
最佳答案
Dijkstra 算法给出了到所有可能的中间节点的成本，以及到汇点的最短路径的成本。您可以通过从汇点到源点(向后)进行深度优先搜索来获取从源点到汇点的所有路径，只有当该边的成本等于成本与从源到两个节点的最短路径。当然，你得到的路径是倒序的，但颠倒它们很容易。
.
关于algorithm - 最短路径不是图中的路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3441829/