需求&方法1（flody算法）

距离矩阵weight_matrix如下，求任意两点之间的最短距离。（有6个点，分别为点1、2、3、4、5、6）

具体操作步骤

①先定义一个flodyWarshall.m函数，具体代码如下：

function [dist, next] = floydWarshall(weight_matrix)
    % 输入: weight_matrix - n x n 的权重矩阵 (Inf 表示不可达)
    % 输出: 
    %   dist - 最短距离矩阵
    %   next - 用于路径重建的下一跳矩阵
    
    n = size(weight_matrix, 1);
    dist = weight_matrix;  % 初始化距离矩阵
    next = zeros(n, n);    % 初始化下一跳矩阵
    
    % 初始化 next 矩阵
    for i = 1:n
        for j = 1:n
            if i == j || weight_matrix(i, j) == Inf
                next(i, j) = -1;  % 不可达或自身
            else
                next(i, j) = j;   % 直接连接
            end
        end
    end
    
    % Floyd-Warshall 核心算法
    for k = 1:n
        for i = 1:n
            for j = 1:n
                if dist(i, k) ~= Inf && dist(k, j) ~= Inf
                    if dist(i, j) > dist(i, k) + dist(k, j)
                        dist(i, j) = dist(i, k) + dist(k, j);
                        next(i, j) = next(i, k);  % 更新下一跳
                    end
                end
            end
        end
    end
End

②再结合距离矩阵写main.m函数如下：

weight_matrix = [
    0    50   Inf    40    25    10;
    50    0    15    20   Inf    25;
   Inf   15     0    10    20   Inf;
    40   20    10     0    10    25;
    25  Inf    20    10     0    55;
    10   25   Inf    25    55     0
];

% 计算所有节点对的最短路径
[dist, next] = floydWarshall(weight_matrix);

% 显示最短距离矩阵
disp("最短距离矩阵 (dist):");
disp(dist);

% 显示下一跳矩阵（用于路径重建）
disp("下一跳矩阵 (next):");
disp(next);

③结果如下：

④分析结果：

• 距离矩阵中，第1行第3个表示：从点1到点3，最短距离为45。
• 如何根据“下一跳矩阵”查点1到点3的路径？
next(1,3)=5，所以第一步走到点5；——>next(5,3)=3，所以第二步走到点3；——>综上可得点1到点5的最短路径为1—5—3。

需求&方法2

下面是一幅图的距离矩阵，求点1到点11的最短路径长度！（dijkstra算法）

具体操作步骤

①先定义一个dijkstra.m函数，具体代码如下

function [min,path]=dijkstra(w,start,terminal)%距离矩阵、开始点、结束点
n=size(w,1); label(start)=0; f(start)=start;
for i=1:n
   if i~=start
       label(i)=inf;
end, end
s(1)=start; u=start;
while length(s)<n
   for i=1:n
      ins=0;
      for j=1:length(s)
         if i==s(j)
            ins=1;
         end,  
      end
      if ins==0
         v=i;
         if label(v)>(label(u)+w(u,v))
            label(v)=(label(u)+w(u,v)); 
         f(v)=u;
         end, 
      end, 
   end   
v1=0;
   k=inf;
   for i=1:n
         ins=0;
         for j=1:length(s)
            if i==s(j)
               ins=1;
            end, 
         end
         if ins==0
            v=i;
            if k>label(v)
               k=label(v);  v1=v;
            end,  
         end,  
   end
   s(length(s)+1)=v1;  
   u=v1;
end
min=label(terminal); path(1)=terminal;
i=1; 
while path(i)~=start
      path(i+1)=f(path(i));
      i=i+1 ;
end
path(i)=start;
L=length(path);
path=path(L:-1:1);