Floyd-Warshall算法是一种动态规划算法,用于寻找加权图中所有顶点对之间的最短路径,能够处理带有负权边的图,但不能处理负权环。
Floyd-Warshall算法是一种用于寻找加权图中所有顶点对之间最短路径的动态规划算法。与Dijkstra或Bellman-Ford等单源最短路径算法不同,Floyd-Warshall算法可以在一次执行中计算出任意两点间的最短距离。算法的核心思想是:对于任意两点i和j之间的最短路径,如果存在一个中间点k,使得从i到k再到j的路径比直接从i到j的路径更短,则更新i到j的最短路径。
假设有一个包含4个顶点(A-D)的有向加权图,边的关系及权重如下:
...