图中最短路径解决方法 Dijkstra

[复制链接]

字体大小: 正常放大

2744557306

798 主题	1 听众	1974 积分

该用户从未签到

电梯直达

1^#

发表于 2023-12-22 11:02 |只看该作者 |正序浏览

|招呼Ta 关注Ta

这段代码是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
[lv,v]=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）进行的，你可能需要根据你的需求更改这个值。