chap图与子图.ppt

* 离散数学 * Floyd算法的程序（1） procedure Shortest; begin for i :=1 to n do for j :=1 to n do begin A[i,j]:=C[i,j]; P[i,j]:= 0 end; for i :=1 to n do A[i,i]:= 0; for k :=1 to n do for i :=1 to n do for j :=1 to n do If A[i,k] + A[k,j] A[i,j] then begin A[i,j] := A[i,k] + A[k,j] P [i,j] := k end end;{Shortest} 初始化 {按顶点的编号进行迭代} {对矩阵按行和列逐个元素修订距离} {若经过顶点k的距离更短，则 修改距离， 并记下该顶点k。} {计算顶点之间的最近距离} 不难看出此程序的时间复杂度为O(n3)。 * 离散数学 * Floyd算法的程序（2） 这是一个递归过程，利用矩阵P[ i , j ]计算i 到j的最短通路: procedure Path(i ,j: integer); var k: integer; begin k:= P [i, j] ; {取出从 i 到 j 的最短通路上的顶点k} If k=0 then return; {i 和 j 邻接，没有中间的顶点} Path(i ,k); {给出从 i 到 k 的最短通路} writeln(k); {输出顶点 k } Path(k ,j) {给出从 k 到 j 的最短通路} end;{Path} 此程序也可不采用递归的方法来实现。请同学们自己设计它的非递归程序，并编程实现。 * 离散数学 * Foloyd算法举例 初始化： A(0) = P= 第一轮： A(1) = A(1)[2,4]:= A(0) [2,1]+ A(0) [1,4] = 40 ＜ A(0) [2, 4] 40 40 A(1)[2,5]:= A(0) [2,1]+ A(0) [1,5] = 110 ＜ A(0) [2, 5] 110 110 P [2,5] := 1 ; P [2,4] := 1 ; * 离散数学 * Foloyd算法举例 第二轮： A(2) = A(2)[1,3]=A(1) [1,2]+A(1)[2,3] = 60 ＜ A(1) [1,3] 60 60 P [1,3]:= 2; 第三轮： A(3) = A(3) [1,5]=A(2)[1,3]+A(2)[3,5] = 70 ＜ A(2) [1,5] 70 70 P [1,5]:= 3; A(3) [2,5]=A(2)[2,3]+A(2)[3,5] = 60 ＜ A(2) [2,5] 60 60 P [2,5]:= 3; A(3) [4,5]=A(2)[4,3]+A(2)[3,5] = 30 ＜ A(2) [4,5] 30 30 P [4,5]:= 3; * 离散数学 * Foloyd算法举例 第四轮： A(4) = A(4) [1,3]=A(3)[1,4]+A(3)[4,3]; = 50 ＜ A(3) [1,3] 50 50 P[1,3]:= 4, A(4) [1,5]=A(3)[1,4]+A(3)[4,5] = 60 ＜ A(3) [1, 5] 60 60 P[1,5]:= 4; 第五轮： A(5) = P = * 离散数学 * 用Floyd算法求最短通路 P = 若要求1?5的最短通路，由程序Path(1, 5)可知： k := P[1, 5] = 4; Path(1, 4); Writeln(k); Path(4, 5) 全过程如右所示： Path(1, 5) Path(1, 4) 4 Path(4, 5) P[1,4]=0 return P[4,5]=3 Path(4,3) 3 Path(3,5) P[4,3]=0 return P[3,5]=0 return P[1,5]=4 加上起点和终点， 1?5的 最短通路为1?4?3?5。 1 2 5 4 3 10 20 50 100 30 10 60 * 离散数学 * 练习：P62 习题30 迭代 S w D[2] D[3] D[4] D[5] D[6] D[7] D[8] D[9] D[10]