大师作文网关于Matlab Dijkstra算法问题,麻烦帮我解释下,
来源：学生作业帮 编辑：大师作文网作业帮 分类：综合作业 时间：2024/11/12 04:07:55
关于Matlab Dijkstra算法问题,麻烦帮我解释下,
第一步：设置初始点,S为已找到最短距离的点集,开始为初始点u0,L（v）为记录各点到初始点u0的距离,设置默认到其他点距离为无穷,便于下面比较
第二步：对于每个不属于S集合的点v,求取L（v）,v到S集合中任意点u的距离W(uv)+L（u）中最小值,这个不难理解吧,就是有通过已经确认是最短路径的点供你选择,你不选么?
第三步：也就是搜索点是否结束的判断,当S中包含所有点时,就可以停止搜索了,这里取i=V-1是因为 S默认已经有原点了,所以还有|V|-1个点需要判断加入到S中
下面给你个实现程序,很久之前写的,是个函数,放在Dijkstra.m文件中,直接调用即可,w为输入矩阵,也就是网络点阵：
% Dijkstra Solution Steps
function [l,z]=Dijkstra(w)
n=size(w,1);
% 赋初值
for i=1:n
l(i)=w(1,i);
z(i)=1;
end
%s为每次搜索到非S中的点到u点的最短距离集合
s=[];
s(1)=1;
u=s(1);
k=1;
%搜索循环运算
while kl(u)+w(u,i)
l(i)=l(u)+w(u,i);
z(i)=u;
end
end
end
%找出非S点中到u点最短路的点v
ll=l;
lv=inf;
for i=2:n
c=find(i==s);
if isempty(c)&ll(i)
第二步：对于每个不属于S集合的点v,求取L（v）,v到S集合中任意点u的距离W(uv)+L（u）中最小值,这个不难理解吧,就是有通过已经确认是最短路径的点供你选择,你不选么?
第三步：也就是搜索点是否结束的判断,当S中包含所有点时,就可以停止搜索了,这里取i=V-1是因为 S默认已经有原点了,所以还有|V|-1个点需要判断加入到S中
下面给你个实现程序,很久之前写的,是个函数,放在Dijkstra.m文件中,直接调用即可,w为输入矩阵,也就是网络点阵：
% Dijkstra Solution Steps
function [l,z]=Dijkstra(w)
n=size(w,1);
% 赋初值
for i=1:n
l(i)=w(1,i);
z(i)=1;
end
%s为每次搜索到非S中的点到u点的最短距离集合
s=[];
s(1)=1;
u=s(1);
k=1;
%搜索循环运算
while kl(u)+w(u,i)
l(i)=l(u)+w(u,i);
z(i)=u;
end
end
end
%找出非S点中到u点最短路的点v
ll=l;
lv=inf;
for i=2:n
c=find(i==s);
if isempty(c)&ll(i)