第十三章 连通图中从一个点出发到其余点的最短路径顶点出发，到其余顶点的最短路(最短距离记为)
Dijkstra(狄克斯特拉)算法：
与相邻的点中，谁最近？不妨设是，则记录下，令；
与S相邻的点中，谁距离最近？该点加入S，并记录下距离；
重复（2），直至全部顶点进入S.
完毕.
手工做 P195之例1 P197之例2
文件名：syp195
clear
a=inf*ones(6,6);
a(1,2)=6;a(1,4)=5;a(1,5)=8;a(2,3)=4;a(2,4)=2;a(3,4)=2;a(3,6)=3;a(4,6)=7;a(5,6)=10;
a(2,1)=6;a(4,1)=5;a(5,1)=8;a(3,2)=4;a(4,2)=2;a(4,3)=2;a(6,3)=3;a(6,4)=7;a(6,5)=10;
n=6;i=1;t(1)=i;jl(1)=0;ddd=ones(1,n);
zx=min(a(i,:));
for j=1:n
if a(i,j)==zx
t(2)=j;jl(j)=zx;break
end
end
[i,t(2),zx]
k=2;ddd(t(1))=0;ddd(t(2))=0;
while k<n
k=k+1;zx=inf;zx1=0;
for j=1:k-1
for l=2:n
aaa=a(t(j),l);
if ddd(l)~=0&aaa<inf
zx1=jl(t(j))+aaa;
if zx1<zx
t(k)=l;zx=zx1;zw=t(j);
end
end
end
end
ddd(t(k))=0;jl(t(k))=zx;[zw,t(k),zx]
end
函数文件：syp195hswj
function syp195hswj(a,i)
n=length(a(1,:));t(1)=i;jl(i)=0;ddd=ones(1,n);
for j=1:n
a(j,j)=inf;
end
zx=min(a(i,:));
for j=1:n
if a(i,j)==zx
t(2)=j;jl(j)=zx;break
end
end
[i,t(2),zx]
k=2;ddd(t(1))=0;ddd(t(2))=0;
while k<n
k=k+1;zx=inf;zx1=0;
for j=1:k-1
for l=1:n
aaa=a(t(j),l);
if ddd(l)~=0&aaa<inf
zx1=jl(t(j))+aaa;
if zx1<zx
t(k)=l;zx=zx1;zw=t(j);
end
end
end
end
ddd(t(k))=0;jl(t(k))=zx;[zw,t(k),zx]
end
文件名：syp197
clear
a=inf*ones(11,11);
a(1,2)=8;a(1,7)=7;a(2,3)=3;a(2,7)=6;a(3,4)=5;a(3,5)=6;
a(4,5)=1;a(4,11)=12;a(5,6)=2;a(5,10)=9;a(6,7)=9;a(6,9)=3;
a(7,3)=5;a(7,8)=10;a(8,1)=8;a(9,5)=7;a(9,8)=9;a(10,9)=2;
a(10,11)=2;a(11,5)=10;
syp195hswj(a,1)
Dijkstra(狄克斯特拉)算法：
与相邻的点中，谁最近？不妨设是，则记录下，令；
与S相邻的点中，谁距离最近？该点加入S，并记录下距离；
重复（2），直至全部顶点进入S.
完毕.
手工做 P195之例1 P197之例2
文件名：syp195
clear
a=inf*ones(6,6);
a(1,2)=6;a(1,4)=5;a(1,5)=8;a(2,3)=4;a(2,4)=2;a(3,4)=2;a(3,6)=3;a(4,6)=7;a(5,6)=10;
a(2,1)=6;a(4,1)=5;a(5,1)=8;a(3,2)=4;a(4,2)=2;a(4,3)=2;a(6,3)=3;a(6,4)=7;a(6,5)=10;
n=6;i=1;t(1)=i;jl(1)=0;ddd=ones(1,n);
zx=min(a(i,:));
for j=1:n
if a(i,j)==zx
t(2)=j;jl(j)=zx;break
end
end
[i,t(2),zx]
k=2;ddd(t(1))=0;ddd(t(2))=0;
while k<n
k=k+1;zx=inf;zx1=0;
for j=1:k-1
for l=2:n
aaa=a(t(j),l);
if ddd(l)~=0&aaa<inf
zx1=jl(t(j))+aaa;
if zx1<zx
t(k)=l;zx=zx1;zw=t(j);
end
end
end
end
ddd(t(k))=0;jl(t(k))=zx;[zw,t(k),zx]
end
函数文件：syp195hswj
function syp195hswj(a,i)
n=length(a(1,:));t(1)=i;jl(i)=0;ddd=ones(1,n);
for j=1:n
a(j,j)=inf;
end
zx=min(a(i,:));
for j=1:n
if a(i,j)==zx
t(2)=j;jl(j)=zx;break
end
end
[i,t(2),zx]
k=2;ddd(t(1))=0;ddd(t(2))=0;
while k<n
k=k+1;zx=inf;zx1=0;
for j=1:k-1
for l=1:n
aaa=a(t(j),l);
if ddd(l)~=0&aaa<inf
zx1=jl(t(j))+aaa;
if zx1<zx
t(k)=l;zx=zx1;zw=t(j);
end
end
end
end
ddd(t(k))=0;jl(t(k))=zx;[zw,t(k),zx]
end
文件名：syp197
clear
a=inf*ones(11,11);
a(1,2)=8;a(1,7)=7;a(2,3)=3;a(2,7)=6;a(3,4)=5;a(3,5)=6;
a(4,5)=1;a(4,11)=12;a(5,6)=2;a(5,10)=9;a(6,7)=9;a(6,9)=3;
a(7,3)=5;a(7,8)=10;a(8,1)=8;a(9,5)=7;a(9,8)=9;a(10,9)=2;
a(10,11)=2;a(11,5)=10;
syp195hswj(a,1)
