第一章 最短路,最少,最多问题.pptVIP

X( 1, 2) 1.000000 0.000000 X( 2, 5) 1.000000 0.000000 X( 3, 7) 1.000000 0.000000 X( 5, 6) 1.000000 0.000000 X( 6, 3) 1.000000 0.000000 X( 7, 10) 1.000000 0.000000 X( 9, 11) 1.000000 0.000000 X( 10, 9) 1.000000 0.000000 即最短路径为 , 最短路长度. 为13 1.2.3 每对顶点之间的最短路 求每对顶点之间最短路的算法是Floyd-warahall算法: 1.算法的基本思路: 直接在图的带权邻接矩阵中用插入顶点的方法依次构造出p个矩阵D(1),D(2), …,D(p),使最后得到的矩阵D(p)成为图的距离矩阵,同时也求出插入点矩阵以便得到两点间的最短路径. 2.算法原理: (1)求距离矩阵的方法: 把带权邻接矩阵W作为距离矩阵的初值,即: D(0)=(dij(0))p×p=W（路径） 10 D(1)=(dij(1)) p×p,其中 dij (1)=min{dij(0),di1(0)+d1j(0)}, dij(1)是从vi到vj的只允许以v1作为中间点的路径中最短路的长度. 20 D(2)=(dij(2)) p×p,其中dij(2)=min{dij(1),di2(1)+d1j(1)}, dij(2),是从vi到vj的只允许以v1,v2作为中间点的路径中最短路的长度. … … … … P0 D(p)=(dij(p)) p×p,其中 dij (p)=min{dij(p-1),dip(p-1)+dpj(p-1)}, dij(p)是从vi到vj的只允许以v1, v2, …, vp作为中间点的路径中最短路的长度.即是从vi到vj中间可插入任何顶点的路径中最短路的长度,因此:D(P)即是距离矩阵. (2)求路由矩阵的方法 在建立距离矩阵的同时可建立路由矩阵R, R=(rij) p×p,rij的含义是从vi到vj的最短路要经过点号为rij的点. R(0)=(rij(0)) p×p, rij(0)=j (走法) 每求得一个D(k)时,按下列方式产生相应的新的R(k): rij (k)= 即当vk被插入任何两点间的最短路径时,被记录在R(k)中,依次求D(p)时求得R(p),可由R(p)来查找任何点对之间最短路的路由. (3)查找最短路路由的方法: 若rij(p)=p1,则点p1是点i到j点的最短路的中间点,然后用同样的方法再分头查找,若: ①向点i追溯得: ②向点j追溯得: 则由点i到j的最短路的路由为:i, pk, …, p2, p1,q1, q2, …, qm, j 3.算法步骤: Floyd算法:求任意两点间的最短路: D(i,j):i到j的距离; R(i, j):i到j的插入点. 输入带权邻接矩阵W(i, j), (1)赋初值;对所有i, j: d(i, j)←W(i, j),r(i, j)←j,k←1 (2)更新d(i, j), r(i, j) :对所有i, j,若: d(i, k)+ d(k, j)d(i, j)则: d(i, j) ← d(i, k)+d(k, j), r(i, j) ← k (3)若k=p,停止;否则:k ← k+1,转(2). 下面给一个程序： Floyd-Warshall算法 Input:非负元素的n×n矩阵[cij] Output: n×n矩阵[dij] ，其中dij是在弧权为cij下，自i到j的最短路长度． Begin for all i≠j do dij:=cij; for i =1, …,n do dij :=∞; for j =1, …, n do for i =1, …, n i ≠ j do for k=1, …, n k≠j do dik:=m