最短路径算法矩阵迭代法matlab代码

最短路径算法是指在图中找到两个顶点之间的最短路径，常见的最短路径算法有 Dijkstra 算法、Bellman-Ford 算法和 Floyd-Warshall 算法等。其中，Floyd-Warshall 算法是一种基于矩阵迭代的动态规划算法，可以求解任意两点之间的最短路径，时间复杂度为 O(n^3)。

以下是 Floyd-Warshall 算法的 Matlab 代码实现：

function [D, P] = floyd_warshall_algorithm(W)
% W: n x n 邻接矩阵，表示有向图或无向图
% D: n x n 矩阵，表示任意两点之间的最短路径长度
% P: n x n 矩阵，表示任意两点之间的最短路径

n = size(W, 1);
D = W;
P = repmat(1:n, n, 1);

for k = 1:n
    for i = 1:n
        for j = 1:n
            if D(i,k) + D(k,j) < D(i,j)
                D(i,j) = D(i,k) + D(k,j);
                P(i,j) = P(k,j);
            end
        end
    end
end