algorithm - 最短路径不是图中的路径

Question

我想知道是否有一种算法可以在图中找到最短路径。

假设我有一个图，其中有几条从一个顶点到另一个顶点的路径。这些路径中的两个或多个具有相同的成本。如何标记、查找等这些顶点之间的所有最短路径？据我所知，Dijkstra 或 Bellman-Ford 算法会找到最短路径，但他们只“选择”一条。

Answer 1

Dijkstra 算法为您提供所有可能的中间节点的成本，以及到汇的最短路径的成本。您可以通过从接收器到源（向后）进行深度优先搜索来获得从源到接收器的所有路径，只有当该边缘的成本等于成本之间的差异时，您才遍历边缘（向后）从源到两个节点的最短路径。当然，您会以相反的顺序获得路径，但是反转它们很容易。

.

Answer 2

看看弗洛伊德-沃歇尔。

在计算机科学中，Floyd-Warshall 算法（有时称为 WFI 算法或 Roy-Floyd 算法）是一种图分析算法，用于在加权图中（具有正边或负边权重）寻找最短路径。算法的单次执行将找到所有顶点对之间最短路径的长度（总权重），尽管它不会返回路径本身的详细信息。该算法是动态规划的一个例子。