用graphshortestpath()函数,可以解决最短路径问题。实现代码如下:
W = [.41 .99 .51 .32 .15 .45 .38 .32 .36 .29 .21]
DG = sparse([6 1 2 2 3 4 4 5 5 6 1],[2 6 3 5 4 1 6 3 4 3 5],W)
h = view(biograph(DG,[],'ShowWeights','on'))
[dist,path,pred] = graphshortestpath(DG,1,6)
给出定点x0到u的最短距离在网络图之中,程序如下:clcclear
%问题:对于无向图实现最短距离
%初始值
%Diikstra算法应用到网络中的最短距离
%求解出父亲点、最短路轻
%创建时间:2020.10.18
w=10111inf infinf inf;%创建邻接矩阵
10 inf 11inf inf inf
Tinf 0 1 inf inf Tinf:
1110111inf
inf 1inf 10 1inf 1:
inf inf inf 110 11
inf inf 11inf 101:
inf inf inf inf 11101
n=size(w.1)
w1=w(1:):
fori=tn
(i)=wT()%贼初值]
(v),Ku0)=0,Ku1)=2,Ku2)=1,Ku3)=8.1(u4)=in
f….
z()=1%这里所求的z(i)-1就是父亲点的意思
end
s-[1
s(1)=1%1代表U0
u=5(1%这里对于我们的u的初始值选取
K=1
%进行循环更新Kv)、z(v)
whilekcn%此处相当于让其初始值不变往下走
%更新(v)、z(v]
fori=tn
for j=Tk
if i"=s(j)
if 1Dak)+wu.i
Ki)=ku)+w(u,D)
zG)=u
end
end
end
end
%第n次更新
11=1%将更新后的|赋值给1目
for i=tn
for j=Tk
ifi”=s(j)%点集出列,不能选择
K)=lKi);%边权不改变
elee
)=inf;%无关联的情况下当前点与具余点的
边权为元穷
end
end
end
lv=inf;%边权赋予给无穷
fori=1n %循环vO到v7寻找vO到v7的最短路
ifj)ly%如果边权点小于无穷,则lv返回i)
的值
lv=Ik)
V=i%顶点集更新,并且赋予给
end
end
lv;%输出边权
v%输出顶点集
s(k+1)=v;%出列点
k=k+1
u=s(k)
end
――
Z
输出结果:
1=
01112223
Z=
11112435
其中代表的是最短路径距离,z表示的是最短路径走向。从上述结果可知,路径为,v1--v2-v5-v8其最短距离为1+2+3=6;所以得知该网络图的最短路距离径为6。对于Dijkstra算法得理解父亲点与距离权重,这是理解算法原理的基础!此代码的好处在于,你根据自己的问题,相应的把邻接矩阵改了就可以用!
用这个程序:m文件function [min,path]=dijkstra(w,start,terminal)
n=size(w,1)label(start)=0f(start)=start
for i=1:n
if i~=start
label(i)=inf
end, end
s(1)=startu=start
while length(s)<n
for i=1:n
ins=0
for j=1:length(s)
if i==s(j)
ins=1
end, end
if ins==0
v=i
if label(v)>(label(u)+w(u,v))
label(v)=(label(u)+w(u,v))f(v)=u
end, end, end
v1=0
k=inf
for i=1:n
ins=0
for j=1:length(s)
if i==s(j)
ins=1
end, end
if ins==0
v=i
if k>label(v)
k=label(v) v1=v
end, end, end
s(length(s)+1)=v1
u=v1
end
min=label(terminal)path(1)=terminal
i=1
while path(i)~=start
path(i+1)=f(path(i))
i=i+1
end
path(i)=start
L=length(path)
path=path(L:-1:1)
调用形式为:
[min,path]=dijkstra(w,start,terminal)
w为邻接矩阵,start为出发点,teminal为终点。
希望帮到你
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)