Floyd-Warshall算法：使用动态规划求解最短路径

Floyd-Warshall算法是一种动态规划算法，用于在加权图中找到所有顶点对之间的最短路径。该算法通过构建一个中间矩阵，逐步更新最短路径长度，最终得到最短路径。与Dijkstra算法相比，Floyd-Warshall算法适用于带负权重的图，并且能够处理不存在最短路径的情况。
在Matlab中实现Floyd-Warshall算法，需要创建一个邻接矩阵来表示图，并定义一个二维数组来存储最短路径长度。以下是使用Matlab实现Floyd-Warshall算法的步骤：

1. 创建一个邻接矩阵来表示图，其中矩阵元素表示两个顶点之间的权重。如果两个顶点之间没有边相连，则将矩阵元素设置为Inf。
2. 初始化一个与邻接矩阵大小相同的二维数组，用于存储最短路径长度。将所有路径长度初始化为Inf，除了起点到起点的路径长度为0。
3. 遍历所有顶点，对于每个顶点作为中间点，更新最短路径长度。对于每个顶点对(i, j)，如果通过中间点k的路径长度更短，则更新最短路径长度。
4. 重复步骤3，直到所有顶点都被遍历完。
5. 输出最短路径长度数组，即为所有顶点对之间的最短路径长度。
   下面是一个简单的Matlab代码示例，演示了如何实现Floyd-Warshall算法：

   function [dist, pred] = floyd_warshall(A)
   % A是一个邻接矩阵，表示带权重的图
   % 返回值dist是一个数组，存储所有顶点对之间的最短路径长度
   % 返回值pred是一个数组，存储每个顶点的最短路径前驱顶点
   n = size(A, 1); % 顶点数
   dist = Inf(n, n); % 初始化最短路径长度数组
   dist(1, :) = A(1, :); % 起点到其他顶点的距离等于边权重
   for k = 1:n
   for i = 1:n
   for j = 1:n
   if dist(i, j) > dist(i, k) + dist(k, j)
   dist(i, j) = dist(i, k) + dist(k, j);
   pred(i, j) = k; % 记录最短路径的前驱顶点
   end
   end
   end
   end
   end

   使用该函数时，需要将邻接矩阵作为输入参数传递给函数，并返回最短路径长度数组和最短路径前驱顶点数组。例如：
   ```matlab
   A = [0 5 Inf; Inf 0 3; Inf Inf 0]; % 邻接矩阵表示带权重的图
   [dist, pred] = floyd_warshall(A); % 调用Floyd-Warshall算法函数
   disp(dist); % 输出最短路径长度数组
   disp(pred); % 输出最短路径前驱顶点数组