图中最短路径解决方法 Dijkstra
这段代码是Dijkstra算法的一个实现，用于在带权图中找到从一个起始点到其他所有点的最短路径。下面是对代码的逐步解释：clear all
%图论最短路问题的Dijkstra算法
%邻接矩阵(点与点的关系)
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);%记录图中点数
for i=1:n
l(i)=w(1,i); %为l(v)赋初值
z(i)=1; %为z(v)赋初值1
end
s=[]; %s集合
s(1)=1; %s集合的第1个元素为起点
u=s(1);
k=1; %k记录集合s中点的数量
while k<n %当集合s未包含所有元素的时候执行循环
for i=1:n %更新一遍l(v),z(v)
if l(i)>l(u)+w(u,i)
l(i)=l(u)+w(u,i);
z(i)=u;
end
end
%找l(i)中最小的v加入s集合
ll=l;
for i=1:n
for j=1:k
if i==s(j)
ll(i)=inf; %去除掉已经在s集合中的点
end
end
end
=min(ll); %求最小的l(v)
s(k+1)=v; %加入集合s
u=v;
k=k+1;
end
fprintf('最短路为:%1d->%1d->%1d->%1d\n',z(z(z(7))),z(z(7)),z(7),7)
解释：
1.清除变量： clear all 语句清除所有之前定义的变量，以确保从干净的状态开始执行程序。
2.邻接矩阵： 图被表示为邻接矩阵 w，其中 w(i, j) 表示从顶点 i 到顶点 j 的边的权重。 inf 表示没有直接的边。
3.初始化： l 数组存储从起始点到每个点的当前最短路径长度，z 数组存储路径中的前一个顶点。初始时，将起始点到每个点的距离初始化，并将前一个顶点初始化为起始点。
4.主循环： 使用 while 循环，每次选择一个新的顶点加入集合 s，直到 s 包含所有顶点。在每次循环中，通过更新 l 和 z 数组来逐步找到最短路径。
5.输出： 最后，使用 fprintf 打印从起始点到指定点的最短路径。在这里，路径是通过回溯 z 数组得到的。
注意：这段代码的输出是针对特定的终点（顶点7）进行的，你可能需要根据你的需求更改这个值。
页:
[1]