第十三章连通图中从一个点出发 到其余点的最短路径 顶点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