Floyd Warshall 算法

Floyd-Warshall算法（英语：Floyd-Warshall algorithm），中文亦称弗洛伊德算法或佛洛依德算法，是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权（但不可存在负权回路）的最短路径问题，同时也被用于计算有向图的传递闭包。

Floyd-Warshall 算法的时间复杂度为 $O(N^{3})$，空间复杂度为 $O(N^{2})$。

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

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

• 若最短路径经过点k，则 $D_{{i,j,k}}=D_{{i,k,k-1}}+D_{{k,j,k-1}}$
• 若最短路径不经过点k，则 $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}})$

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