多源最短路径 – Floyd-Warshall Algorithm

介绍：

　　是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权（但不可存在负权回路）的最短路径问题，同时也被用于计算有向图的传递闭包。

　　Floyd-Warshall算法的时间复杂度是O(N³),空间复杂度O(N²)。

原理：

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

　　用f^k(i,j)表示从 i 到 j 只以(1...k)集合中的节点为中间节点的最短距离，这样从f^k-1(i,j)推出f^k(i,j)就很容易了。

　　1^°若最短路径经过点k，f^k(i,j) = f^k-1(i,k) + f^k-1(k,j)

　　2^°若最短路径不经过点k，f^k(i,j) = f^k-1(i,j)

　　因此f^k(i,j) = min(f^k-1(i,j) , f^k-1(i,k) + f^k-1(k,j))。

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

算法描述：

其他作用：

　　在有向图中，有时不必关心路径的长度，而只关心每两点间是否有通路，则可以用1和0分别代表“连通”和“不连通”。这样除了预处理需要做少许调整外，主算法只需把“d[i][j] = min( d[i][j] , d[i][k] + d[k][j] )”改成“d[i][j] = d[i][j] || (d[i][k] && d[k][j])”。这样的结果称为有向图的传递闭包。

　　还可以求最小环。

巴特西

多源最短路径 – Floyd-Warshall Algorithm

最新文章

热门文章