Ford 算法来找到源点到其他各点的最短路径
这段代码是Floyd-Warshall算法的一个实现，用于在带权图中找到所有顶点对之间的最短路径。让我逐步解释每一部分：% 邻接矩阵(点与点的关系)w=[0,2,4,inf,inf,inf,inf;
2,0,inf,3,3,1,inf;
4,inf,0,2,3,1,inf;
inf,3,2,0,inf,inf,1;
inf,3,3,inf,0,inf,3;
inf,1,1,inf,inf,0,4;
inf,inf,inf,1,3,4,0];
n=size(w,1); % n记录图中点数
D=w; % D为距离矩阵
R=[]; % R为路径矩阵
for i=1:n
for j=1:n
R(i,j)=j; % 为R矩阵赋初值
end
end
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);
R(i,j)=k;
end
end
end
endD % 输出距离矩阵
R % 输出路径矩阵
解释：
1.带权图的表示： 给定图被表示为邻接矩阵 w，其中 w(i, j) 表示从顶点 i 到顶点 j 的边的权重。inf 用于表示两个顶点之间没有直接的边。
2.初始化： 距离矩阵 D 被初始化为与邻接矩阵相同的值。路径矩阵 R 被初始化为一个矩阵，其中每个元素 R(i, j) 最初被设置为 j。
3.Floyd-Warshall算法： 嵌套循环实现了Floyd-Warshall算法。外层循环 (k) 代表通过哪个中间顶点进行路径检查。内层循环 (i 和 j) 遍历所有顶点对，并检查通过 k 从 i 到 j 的路径是否比直接从 i 到 j 的路径更短。如果是这样，就更新距离矩阵 D 和路径矩阵 R。
4.输出： 最终的距离矩阵 D 和路径矩阵 R 被显示。
输出包含最终的距离矩阵和表示路径的矩阵。元素 D(i, j) 表示从顶点 i 到顶点 j 的最短距离，而 R(i, j) 表示从 i 到 j 的最短路径上的中间顶点。
页:
[1]