【MATLAB】最短路径Floyd算法

∙ \bullet ∙ 求每队顶点的最短路径

∙ \bullet ∙ 有向图、无向图和混合图

直接在图的带权邻接矩阵中用插入顶点的方法依次递推地构造出n个矩阵D(1)，D(2)…D(n)（每次加入一个点然后更新最短路径矩阵D），D(n)是图的最短距离矩阵，同时引入一个后继点矩阵path记录两点间的最短路径。

对于如下无向图： 我们可以得如下带权邻接矩阵： [ 0 7 9 i n f i n f 14 7 0 10 15 i n f i n f 9 10 0 11 i n f 2 i n f 15 11 0 6 i n f i n f i n f i n f 6 0 9 14 i n f 2 i n f 9 0 ] \begin{bmatrix} 0 & 7 & 9 & inf & inf & 14\\ 7 & 0 & 10 &15 & inf & inf\\ 9 & 10 & 0 & 11 & inf & 2\\ inf & 15 & 11 & 0 & 6 & inf\\ inf & inf & inf & 6 & 0 & 9\\ 14 & inf & 2 & inf & 9 & 0\\ \end{bmatrix} ⎣⎢⎢⎢⎢⎢⎢⎡​079infinf14​701015infinf​910011inf2​inf151106inf​infinfinf609​14inf2inf90​⎦⎥⎥⎥⎥⎥⎥⎤​

实现步骤：

∙ \bullet ∙ 变量：输入变量与输出变量

∙ \bullet ∙ 赋初值：对所有的i、j， D ( i , j ) = w ( i , j ) , p a t h ( i , j ) = j , k = 1 ( k 表 示 加 入 的 顶 点 个 数 ) D(i,j)=w(i,j),path(i,j)=j,k=1(k表示加入的顶点个数) D(i,j)=w(i,j),path(i,j)=j,k=1(k表示加入的顶点个数)

∙ \bullet ∙ 更新D(i,j)、path(i,j)，对于所有i、j，若 D ( i , k ) + D ( k , j ) < D ( i , j ) D(i,k)+D(k,j)6

∙ \bullet ∙ 接着我们就要找 path(6,5)=5，到达终点，所以最终路径为1->3->6->5

注意：调用floyd函数的时候，同时还会输出每次插入一个顶点之后D矩阵和path矩阵的变化。