E701359676051C36257A5077685520FD34B

C(a)

E7060513667776857CE13(2)5913(2)2(1)FA2(1)55A50(5)F20(3)20(3)50(5)D34(4)BD34(4)B

(b) (c)

图9-45

9.14 解：在图中没有负赋权，因此采用Dijkstra算法，步骤如下： vjk?1 v10*v2??v?Vv3??v4v5v6v7v8v9 L1(vj)???????????? v*?v1，d(v1,v1)?L1(v*)?minL1(vj)?0；

vjk?2 v10*v23*v?Av3??v44v5v6v7v8v9 L2(vj)?????????? v*?v2，d(v1,v2)?L2(v*)?minL2(vj)?3，前列顶点v1；

vjk?3 v10*v23*v?Av36v44*v55v66v7v8v9 L3(vj)?????? v*?v4，d(v1,v4)?L3(v*)?minL3(vj)?4，前列顶点v1；

vjk?4 v10*v23*v?Av36v44*v55*v66v77v8v9 L4(vj)???? v*?v5，d(v1,v5)?L4(v*)?minL4(vj)?5，前列顶点v2；

41

vj k?5 v10*v23*v?Av36*v44*v55*v66v77v8v9 L5(vj) ???? v*?v3，d(v1,v3)?L5(v*)?minL5(vj)?6，前列顶点v2；

vjk?6 v10*v23*v?Av36*v44*v55*v66*v77v8??v9 11 L6(vj)v*?v6，d(v1,v6)?L6(v*)?minL6(vj)?6，前列顶点v2；

vjk?7 v10*v23*v?Av36*v44*v55*v66*v77*v8??v9 8.5 L7(vj)v*?v7，d(v1,v7)?L7(v*)?minL7(vj)?7，前列顶点v4；

vjk?8 v10*v23*v36*v44*v55* v66*v77*v89v9 8.5*L8(vj)v*?v9，d(v1,v9)?L8(v*)?minL8(vj)?8.5，前列顶点v6。

v?A综合以上过程，得到顶点v1到v9最短路径为v1?v2?v6?v9，长度为8.5。 9.15 解：在图中没有负赋权，采用Dijkstra算法，步骤如下： vjk?1 v10*v2??v3??v?Vv4v5v6v7v8v9v10v11 L1(vj)???????????????? v*?v1，d(v1,v1)?L1(v*)?minL1(vj)?0；

vjk?2 v10*v22*v3??v?Av48v5v6v7v8v9v10v11 L2(vj)?????????????? v*?v2，d(v1,v2)?L2(v*)?minL2(vj)?2，前列顶点v1； k?3 vj v1v2v3v4v5v6v7v8v9v10v11 42

L3(vj) 0*2*??v?A83*???????????? v*?v5，d(v1,v5)?L3(v*)?minL3(vj)?3，前列顶点v2；

vjk?4 v10*v22*v3??v?Av48v5v6v7v8v9v10v11 L4(vj)3*??????4*???? v*?v9，d(v1,v9)?L4(v*)?minL4(vj)?4，前列顶点v5；

vj k?5 v10*v22*v3??v?Av48*v53*v610v7??v811v9v10v11 L5(vj) 4*???? v*?v4，d(v1,v4)?L5(v*)?minL5(vj)?8，前列顶点v1；

vjk?6 v10*v22*v315v?Av48*v53*v6v7v8v9v10v11 L6(vj)10*??114*???? v*?v6，d(v1,v6)?L6(v*)?minL6(vj)?10，前列顶点v9；

vjk?7 v10*v22*v315v?Av48*v53*v610*v714v8v9v10v11 L7(vj)11*4*???? v*?v8，d(v1,v8)?L7(v*)?minL7(vj)?11，前列顶点v9；

vjk?8 v10*v22*v315v?Av48*v53*v610*v714*v8v9v10v11 L8(vj)11*4*??20 v*?v7，d(v1,v7)?L8(v*)?minL8(vj)?14，前列顶点v6。

vjk?9 v10*v22*v315v?Av48*v53*v610*v714*v8v9v10v11 L9(vj)11*4*15*20 v*?v10，d(v1,v10)?L9(v*)?minL9(vj)?15，前列顶点v7。

k?10 vj v1v2v3v4v5v6v7v8v9v10v11 43

L10(vj) 0*2*15*v?A8*3*10*14*11*4*15*20 v*?v3，d(v1,v3)?L10(v*)?minL10(vj)?15，前列顶点v4。

vjk?11 v10*v22*v315*v48*v53*v610*v714*v8v9v10v11 L11(vj) 11*4*15*20* v*?v11，d(v1,v11)?L11(v*)?minL11(vj)?20，前列顶点v8。

v?A综合以上过程，得到顶点v1到其他各顶点的最短路径和长度分别为：

v1?v2,d(v1,v2)?2

v1?v4?v3,d(v1,v3)?15

v1?v4,d(v1,v4)?8

v1?v2?v5,d(v1,v5)?3

v1?v2?v5?v9?v6,d(v1,v6)?10 v1?v2?v5?v9?v6?v7,d(v1,v7)?14 v1?v2?v5?v9?v8,d(v1,v8)?11 v1?v2?v5?v9,d(v1,v9)?4

v1?v2?v5?v9?v6?v7?v10,d(v1,v10)?15 v1?v2?v5?v9?v8?v11,d(v1,v11)?20

v221v51v879v47v1v6468v9v11v3v71v10 图9-46

9.16 解：采用Dijkstra算法，步骤如下： vjk?1 v10*v2??v?Vv3??v4v5v6v7v8 L1(vj)?????????? v*?v1，d(v1,v1)?L1(v*)?minL1(vj)?0； k?2 vj v1v2v3v4v5v6v7v8 44