我想知道是否有一种算法可以在图中找到最短路径 .
假设我有一个图表，其中有一对从一个顶点到另一个顶点的路径 . 这些路径中的两个或更多个具有相同的成本 . 如何标记，找到这些顶点之间的所有最短路径？据我所知，Dijkstra或Bellman-Ford算法将找到最短路径，但他们只“选择”一个 .
Dijkstra的算法为您提供了所有可能的中间节点的成本，以及到接收器的最短路径的成本 . 您可以通过从接收器到源（向后）进行深度优先搜索来获取从源到接收器的所有路径，只有当该边缘的成本等于成本之间的差异时才能遍历边缘（向后） . 从源到两个节点的最短路径 . 当然，你以相反的顺序获得路径，但是反转它们很容易 .
.
看看Floyd-Warshall .
在计算机科学中，Floyd-Warshall算法（有时称为WFI算法或Roy-Floyd算法）是用于在加权图中找到最短路径的图分析算法（具有正边缘权重或负边缘权重） . 算法的单次执行将找到所有顶点对之间的最短路径的长度（总和权重），尽管它不返回路径本身的细节 . 该算法是动态编程的一个例子 .
2 回答
Dijkstra的算法为您提供了所有可能的中间节点的成本，以及到接收器的最短路径的成本 . 您可以通过从接收器到源（向后）进行深度优先搜索来获取从源到接收器的所有路径，只有当该边缘的成本等于成本之间的差异时才能遍历边缘（向后） . 从源到两个节点的最短路径 . 当然，你以相反的顺序获得路径，但是反转它们很容易 .
.
看看Floyd-Warshall .