弗洛伊德matlab算法

弗洛伊德算法是一种用于解决图中任意两点之间最短路径问题的算法。该算法通过动态规划的方式逐步更新图中各个节点之间的最短路径长度。其基本思想是，通过每个节点作为中介，不断优化和更新两个节点之间的最短路径。

在Matlab中实现弗洛伊德算法的代码如下所示：

function [dist,mypath]=myfloyd(a,sb,db)
% 输入邻接矩阵a；元素a(i,j)——顶点i到j之间的直达距离，可以是有向的
% sb起点的标号；db终点的标号
% 输出：dist——最短的距离
% mypath——最短的路径
% 优点可以求出任意两点之间的最短路缺点就是慢
n=size(a,1);
path=zeros(n);
for k=1:n
  for i=1:n
    for j=1:n
      if a(i,j)>a(i,k)+a(k,j) % 如果经过中介节点k可以找到更短的路径
        a(i,j)=a(i,k)+a(k,j); % 更新最短路径长度
        path(i,j)=k; % 记录中介节点
      end
    end
  end
end

% 得path矩阵对于path(i,j)的值表示如果要从i到j,j的前一个节点，然后看path(i,path(i,j)(即前一个节点的值))
% 依次倒推找到最短路径
dist = a(sb,db);
parent = path(sb,:); % 从起点sb到终点db的最短路上各顶点的前驱顶点
parent(parent==0)=sb; % path中的分量为0，表示该顶点的前驱是起点
mypath = db;
t = db;
while t~=sb
  p = parent(t);
  mypath = [p,mypath]; % 从终点到起点倒着记录
  t = p;
end
end

这段代码实现了弗洛伊德算法，并返回了最短距离和最短路径。其中，输入参数`a`是邻接矩阵，`sb`是起点的标号，`db`是终点的标号。输出参数`dist`是最短距离，`mypath`是最短路径。通过调用该函数，你可以得到任意两点之间的最短路径。<span class="em">1</span>