第十三章连通图中从一个点出发 到其余点的最短路径 顶点u出发,到其余顶点u的最短路最短距离记为/) Dijkstra(狄克斯特拉)算法: (1)与a1相邻的点中,谁最近?不妨设是ak,则记 录下l4,令S={4,l}; (2)与S相邻的点中,谁距离u最近?该点加入S, 并记录下距离 (3)重复(2),直至全部顶点进入S 完毕 手工做P195之例1P197之例2 文件名:syp195 ear a=inf*ones(6, 6) (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 (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;j1(1)=0;dd=ones(l,n) Zx=min(a(i,: ) for j=l:n f a(i, j) t(2)=j; jl (j)=zx break nd i,t(2),zx] k=2;ddd(t(1))=0;dd(t(2)=0 while k<n k=k+l: zx=inf: zx1=0 for j=l: k-1 for 1=2: n aaa=a(t(j), 1) if ddd(1)=O&aaa<inf zx1=jl(t(j))+aaa f zxI<zx t( k)=l; zx=Zxl; zw=t(j) ddd(t(k))=0; jl(t(k))=zx: [zW, t(k), zx]
第十三章 连通图中从一个点出发 到其余点的最短路径 顶点 1 u 出发，到其余顶点 i u 的最短路(最短距离记为 i l ) Dijkstra(狄克斯特拉)算法： （1） 与 1 u 相邻的点中，谁最近？不妨设是 k u ，则记 录下 k l ，令 S = u1 ,uk ； （2） 与 S 相邻的点中，谁距离 1 u 最近？该点加入 S， 并记录下距离； （3） 重复（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, 1) n=length(a(l, );t(1)=i; jl (i)=0; ddd ones for j=l:n a (j, j)=inf end zx=min(a(i,: fo if a(i, j)==zx t(2)=j: jl(j)=zx;break en d [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=l: k-1 for 1=1: n if ddd(1)=0&aaa<inf zx1=jl(t(j))+aaa if zxI<zx t( k)=l; zx=zxl; zw=t(j) end ddd(t(k))=0; jl(t(k))=zx: [Zw, t(k), zx] en 文件名:sypl 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 )=9;a(6,9) 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)
函数文件：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)