在前面章节中,我们介绍了Floyd算法。Floyd算法是解决任意两点间的最短路径的一种算法,可以正确处理有向图或负权的最短路径问题,同时也被用于计算有向图的传递闭包。
Floyd算法的时间复杂度为O(N^3),空间复杂度为O(N^2)。
Floyd算法也一个经典的动态规划算法。假设,我们的目标是寻找从点i到点j的最短路径,那么从动态规划的角度看,我们需要为这个目标重新做一个诠释。
1. Floyd算法思想
从任意节点i到任意节点j的最短路径不外乎2种可能:一种是直接从i到j,另外一种是是从i经过若干个节点k到j。所以,假设Dis(i,j)为节点u到节点v的最短路径的距离,对于每一个节点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的最短路径的距离。
Floyd算法实现原理如下:
l 从任意一条单边路径开始。所有两点之间的距离是边的权,如果两点之间没有边相连,则权为无穷大。
l 对于每一对顶点 u 和 v,看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。
2. Floyd算法如何应用动态规划
在动态规划算法中,处于首要位置、且也是核心理念之一的就是状态的定义。在这里,把d[k][i][j]定义成:
“只能使用第1号到第k号点作为中间媒介时,点i到点j之间的最短路径长度。”
图中共有n个点,标号从1开始到n。因此,在这里,k可以认为是动态规划算法在进行时的一种层次,或者称为“松弛操作”。d[1][i][j]表示只使用1号点作为中间媒介时,点i到点j之间的最短路径长度;d[2][i][j]表示使用1号点到2号点中的所有点作为中间媒介时,点i到点j之间的最短路径长度;d[n-1][i][j]表示使用1号点到(n-1)号点中的所有点作为中间媒介时,点i到点j之间的最短路径长度d[n][i][j]表示使用1号到n号点时,点i到点j之间的最短路径长度。有了状态的定义之后,就可以根据动态规划思想来构建动态转移方程。
动态转移的基本思想可以认为是建立起某一状态和之前状态的一种转移表示。按照前面的定义,d[k][i][j]是一种使用1号到k号点的状态,可以想办法把这个状态通过动态转移,规约到使用1号到(k-1)号的状态,即d[k-1][i][j]。对于d[k][i][j](即使用1号到k号点中的所有点作为中间媒介时,i和j之间的最短路径),可以分为两种情况:(1)i到j的最短路不经过k;(2)i到j的最短路经过了k。不经过点k的最短路情况下,d[k][i][j]=d[k-1][i][j]。经过点k的最短路情况下,d[k][i][j]=d[k-1][i][k]+d[k-1][k][j]。因此,综合上述两种情况,便可以得到Floyd算法的动态转移方程:
d[k][i][j] = min(d[k-1][i][j],d[k-1][i][k]+d[k-1][k][j])(k,i,j∈[1,n])
最后,d[n][i][j]就是所要求的图中所有的两点之间的最短路径的长度。在这里,需要注意上述动态转移方程的初始(边界)条件,即d[0][i][j]=w(i, j),也就是说在不使用任何点的情况下(“松弛操作”的最初),两点之间最短路径的长度就是两点之间边的权值(若两点之间没有边,则权值为INF,且我比较偏向在Floyd算法中把图用邻接矩阵的数据结构来表示,因为便于操作)。当然,还有d[i][i]=0(i∈[1,n])。这样我们就可以编写出最为初步的Floyd算法代码。





































苏公安网备 32011402010933号