4.4 图的基本应用及其复杂度分析

　　习题3分析：
　　设S为最短距离已确定的顶点集，则V-S是最短距离尚未确定的顶点集，增加一个辅助向量D，它的每个分量D[i]表示当前已知的从源点V0到终点i(i=0,1,2,3,4,5)的最短路径长度。
　　初始时S={V0}，V-S={V1,V2,V3,V4,V5}，D={0,∞,∞,∞,∞,∞}。
　　（1）第1步操作：
　　初始状态：S={V0}，V-S={V1,V2,V3,V4,V5}，D={0,∞,∞,∞,∞,∞}。
　　计算D：
　　顶点V1
　　分析V0：D[0]+A[0,1]=∞=D[1]=∞，所以D[1]不变。
　　顶点V2
　　分析V0：D[0]+A[0,2]=10 < D[2]=∞，所以D[2]=10。
　　顶点V3
　　分析V0：D[0]+A[0,3]=∞= D[3]=∞，所以D[3]不变。
　　顶点V4
　　分析V0：D[0]+A[0,4]=30 < D[4]=∞，所以D[4]=30。
　　顶点V5
　　分析V0：D[0]+A[0,5]=100 < D[5]=∞，所以D[5]=100。
　　计算后的D：
　　D={0,∞,10,∞,30,100}。
　　加入集合S的操作：最小的D[i]（i∈V-S）是D[2]=10，所以顶点V2加入集合S。
　　终态：S={V0,V2}，V-S={ V1,V3,V4,V5}，D={0,∞,10,∞,30,100}。
　　（2）第2步操作：
　　初始状态：S={V0,V2}，V-S={ V1,V3,V4,V5}，D={0,∞,10,∞,30,100}。
　　计算D：
　　顶点V1
　　分析V2：D[2]+A[2,1]=10+∞= D[1] = ∞，所以D[1]不变。
　　顶点V3
　　分析V2：D[2]+A[2,3]=10+50 < D[3] = ∞，所以D[3]=60。
　　顶点V4
　　分析V2：D[2]+A[2,4]=10+∞ > D[4] = 30，所以D[4]不变。
　　顶点V5
　　分析V2：D[2]+A[2,5]=10+∞ > D[5] = 100，所以D[5]不变。
　　计算后的D：
　　D={0,∞,10,60,30,100}。
　　加入集合S的操作：最小的D[i]（i∈V-S）是D[4]=30，所以顶点V4加入集合S。
　　终态：S={V0,V2,V4}，V-S={ V1,V3,V5}，D={0,∞,10,60,30,100}。
　　（3）第3步操作：
　　初始状态：S={V0,V2,V4}，V-S={ V1,V3,V5}，D={0,∞,10,60,30,100}。
　　计算D：
　　顶点V1
　　分析V4：D[4]+A[4,1]=30＋∞ =D[1] = ∞，所以D[1]不变。
　　顶点V3
　　分析V4：D[4]+A[4,3]=30＋20 < D[3] = 60，所以D[3]=50。
　　顶点V5
　　分析V4：D[4]+A[4,5]=30＋60 < D[5] = 100，所以D[5]=90。
　　计算后的D：
　　D={0,∞,10,50,30,90}。
　　加入集合S的操作：最小的D[i]（i∈V-S）是D[3]=50，所以顶点V3加入集合S。
　　终态：S={V0,V2,V3,V4}，V-S={ V1,V5}，D={0,∞,10,50,30,90}。
　　（4）第4步操作。
　　初始状态：S={V0,V2,V3,V4}，V-S={ V1,V5}，D={0,∞,10,50,30,90}。
　　计算D：
　　顶点V1
　　分析V3：D[3]+A[3,1]=50+∞ ＝ D[1] = ∞，所以D[1]不变。
　　顶点V5
　　分析V3：D[3]+A[3,5]=50＋10 < D[5] = 90，所以D[5]=60。
　　计算后的D：
　　D={0,∞,10,50,30,60}。
　　加入集合S的操作：最小的D[i]（i∈V-S）是D[5]=60，所以顶点V5加入集合S。
　　终态：S={V0,V2,V3,V4,V5}，V-S={V1}，D={0,∞,10,50,30,60}。
　　由于集合VS中只有顶点V1，而D[1]=∞，所以最短路径查询算法结束。
　　综上所述，求解顶点V0到其他顶点的最短路径的步骤、最短路径顶点序列和路径长度如
　　表4-8所示。
 

表4-8  从顶点V0到各终点的D值和最短路径求解过程