用floyd算法求图中任意两点最短距离（matlab）

先将如图所示的点和距离转换成临接矩阵的图

 

 matlab代码

clc, clear, a = zeros(4);
a(1,[3,4])=[10,60];  %输入邻接矩阵的上三角元素
a(2,[3,4])=[5,20]; a(3,4)=1;%将点输入4*4元素都为0的矩阵当中
 
n=length(a); b=a+a';  %构造完整的邻接矩阵，矩阵转置后相加
n
b(b==0)=inf; %把矩阵b中所有零元素换成inf
b
b(1:n+1:end)=0; %把对角线元素换成0  ,n为4，n+1=5，每次加5即b(1)=0,b(6)=0,b(11)=0,b(16)=0
b              %b（5）相当于b（1,1）
for k=1:n  %floyd的核心算法 
    for i=1:n
        for j=1:n
            if b(i,k)+b(k,j)
                b(i,j)=b(i,k)+b(k,j);
            end
        end
    end
end
b  %显示两两顶点之间的最短距离

举个简单例子，n在这里面相当于3，k一共取3次，从0，1，2，，首先是0时表示绿色的行和列的值不改变，以0为（中转点），其他点到达中转点距离不变，所有这个代表了k从1到n最外面的大for循环。其次，两个嵌套的for循环i和j代表了除开绿色线覆盖矩阵内的点，即上图的右下角0 4 无穷 0 的矩阵。依次遍历，若找到13+10<4 则令 13+10的结果取替换4 ，但明显图中不是，不替换所以继续遍历。 b(i,k)+b(k,j)  b(i,j)=b(i,k)+b(k,j); 你细品。

 当k=1时，此刻是最外面大for循环遍历+1，此刻1作为中转节点，绿色区域内值不变，

判断从0到2这个点间的距离开始，原本为13，但此刻利用中转点1，改变为了 0到1（6），再从1到2（4） 4+6=10<13 满足条件，因此替换。

此算法通过3个for循环，时间复杂度为n^3。建议观看下方b站链接学习。

for k=1:n  %floyd的核心算法 
    for i=1:n
        for j=1:n
            if b(i,k)+b(k,j)<b(i,j)
                b(i,j)=b(i,k)+b(k,j);
            end
        end
    end
end

这个b站up讲得特别好：链接下方

求最短路径Floyd算法！_哔哩哔哩_bilibili