Floyd-Warshall全源最短路径算法
介绍
Floyd-Warshall算法是一种用于寻找加权图中所有顶点对之间最短路径的动态规划算法。与Dijkstra或Bellman-Ford等单源最短路径算法不同,Floyd-Warshall算法可以在一次执行中计算出任意两点间的最短距离。算法的核心思想是:对于任意两点i和j之间的最短路径,如果存在一个中间点k,使得从i到k再到j的路径比直接从i到j的路径更短,则更新i到j的最短路径。
算法步骤
- 初始化距离矩阵:对于所有顶点对(i,j),如果存在从i到j的边,距离为该边的权重;如果i==j,距离为0;否则距离为无穷大
- 对于每个顶点k(作为中间点):
- 对于每对顶点i和j:
- 如果dist[i][j] > dist[i][k] + dist[k][j],则更新dist[i][j] = dist[i][k] + dist[k][j]
- 最终dist[i][j]包含从顶点i到顶点j的最短路径长度
算法详解
假设有一个包含4个顶点(A-D)的有向加权图,边的关系及权重如下:
- A到B,权重为3
- A到C,权重为6
- B到C,权重为2
- B到D,权重为4
- C到D,权重为1
- D到A,权重为5
...