Floyd-Warshall算法

原理

Floyd-Warshall 算法的原理是动态规划 。

设 D i , j , k {\displaystyle D_{i,j,k}} 为从 i {\displaystyle i} 到 j {\displaystyle j} 的只以 ( 1.. k ) {\displaystyle (1..k)} 集合中的节点为中间节点的最短路径的长度。

若最短路径经过点k，则 D i , j , k = D i , k , k − − --> 1 + D k , j , k − − --> 1 {\displaystyle D_{i,j,k}=D_{i,k,k-1}+D_{k,j,k-1}} ；

若最短路径不经过点k，则 D i , j , k = D i , j , k − − --> 1 {\displaystyle D_{i,j,k}=D_{i,j,k-1}} 。

因此， D i , j , k = min ( D i , j , k − − --> 1 , D i , k , k − − --> 1 + D k , j , k − − --> 1 ) {\displaystyle D_{i,j,k}={\mbox{min}}(D_{i,j,k-1},D_{i,k,k-1}+D_{k,j,k-1})} 。

在实际算法中，为了节约空间，可以直接在原来空间上进行迭代，这样空间可降至二维。

算法描述

Floyd-Warshall 算法的描述如下：

其中 dist[i][j] 表示由点 i {\displaystyle i} 到点 j {\displaystyle j} 的代价，当其为 ∞ 表示两点之间没有任何连接。

参见

图论最短路

Dijkstra算法

Bellman-Ford算法

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。