弗洛伊德算法例题图解,弗洛伊德算法属于什么算法

Floyd算法（弗洛伊德算法）是解决任意两点间的最短路径的一种很有代表性的算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。该算法名称以创始人之一，1978年图灵奖获得者，斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。该算法也称为Floyd-Warshall算法、Roy-Warshall算法、Roy-Floyd算法或WFI算法。

Floyd算法又称为插点法，是一个经典的动态规划算法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法。所谓多源点是与单源点相对来讲的，单源点是指从一个起始点到其它所有点，多源点是指任意两点之间。

都是最短路径算法。

1. 从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。
2. 对于每一对结点 i 和 j，看看是否存在一个结点k 使得从 i 到 k 再到 j 比已知的路径更短，如果是更新它。

从任意结点i到任意结点j的最短路径不外乎两种可能：

• 直接从i到j；
• 从i经过若干个结点k到j。

所以，我们假设Dis(i,j)为结点i到结点j的最短路径的距离，对于每一个结点k，我们检查Dis(i,k) Dis(k,j) < Dis(i,j)是否成立，如果成立，证明从i到k再到j的路径比i直接到j的路径短，我们便设置Dis(i,j) = Dis(i,k) Dis(k,j)，这样一来，当我们遍历完所有结点k，Dis(i,j)中记录的便是i到j的最短路径的距离。所以这实际上将大规模的问题自顶向下划分为了小规模的问题，这就是动态规划思想，状态转移方程是 Dis[i,j]:=min{ Dis[i,k] Dis[k,j]，Dis[i,j] }。

题目：求图4-1中各点相互之间的最短距离？

图4-1

第1步，根据加权连通图，创建矩阵S。当任意两点之间不允许经过第三个点时，这些结点之间最短距离就是初始距离，默认没有直接相连的两结点之间初始距离是INF(无穷大)。如图4-2所示。

图4-2

第2步，以结点A为中介点，只允许经过结点A，求任意两点之间的最短距离，应该如何求呢？只需判断S[i][A] S[A][j]是否比S[i][j]要小即可。S[i][j]表示的是从结点i到结点j之间的距离。S[i][A] S[A][j]表示的是从结点i先到结点A，再从结点A到结点j的距离之和。伪代码表示如下：

for(i=A; i<=G; i ) for(j=A; j<=G; j ) { if (S[i][j] > S[i][A] S[A][j]) S[i][j] = S[i][A] S[A][j]; }

更新矩阵S。如图4-3所示。

图4-3

第3步，以结点B为中介点，只允许经过结点A和B，求任意两点之间的最短距离，应该如何求呢？在求得图4-3矩阵S的前提下，只需判断S[i][B] S[B][j]是否比S[i][j]要小即可。S[i][j]表示的是从结点i到结点j之间的距离。S[i][B] S[B][j]表示的是从结点i先到结点B，再从结点B到结点j的距离之和。伪代码表示如下：

for(i=A; i<=G; i ) for(j=A; j<=G; j ) { if (S[i][j] > S[i][B] S[B][j]) S[i][j] = S[i][B] S[B][j]; }

更新矩阵S。如图4-4所示。