第七章图（Graphs）.pptVIP

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 终点 从V0到各终点D值和最短路径的求解过程 V1 V2 V3 V4 Vj V5 i=1 V2 ? 10 (V0 ,V2) 30 (V0 ,V4) 100 (V0 ,V5) {V0 ,V2} ? S ? 30 (V0 ,V4) 100 (V0 ,V5) 60 (V0 ,V2,,V3) {V0 ,V2,V4} V4 i=2 ? i=5 50 (V0 ,V4 ,V3) 90 (V0 ,V4 ,V5) V3 ? i=3 {V0,V2,V3,V4} V5 60 (V0 ,V4 ,V3 ,V5) ? i=4 {V0,V2,V3,V4,V5} v0 v1 v2 v3 v4 v5 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 1 1 0 1 0 0 0 1 0 1 0 0 1 1 1 v0-v0 v0-v1 v0-v2 v0-v3 v0-v4 v0-v5 DIJ算法实现： { for(v=0; vG.vexnum; ++v) { final[v] = FALSE; D[v] = G.arcs[v0][v]; for(w=0; wG.vexnum; ++w) P[v][w] = FALSE; // 设空路径 if (D[v]INFINITY) { p[v][v0]=TRUE; p[v][v] = TRUE; } }// for D[v0] = 0; final[v0] = TRUE; // 初始化，v0顶点属于S集 void ShortesPath_DIJ(MGraph G, int v0, PathMatrix P, ShortPathTable D ) 若w是从v0到v最短路径上的顶点,则p[v][w]为TRUE 已经求得从v0到v的最短路径,final[v]为TRUE // 开始主循环，每次求得v0到某个v顶点的最短路径，并加v到S集 for (i=1; iG.vexnum; ++i) // 其余G.vexnum-1个顶点 { min = INFINITY; //当前离v0顶点的最近距离 for(w=0;wG.vexnum; ++w) if (! final[w]) // w顶点在V -S中 if(D[w]min) { v = w; min = D[w]; } // w顶点离v0顶点更近 final[v] = TRUE; // 离v0顶点最近的v加入S for(w=0; wG.vexnum; ++w) //更新当前最短路径及距离 if(! final[w] (min+G.arcs[v][w]D[w])) { D[w] = min + G.arcs[v][w]; //修改D[w]和P[w],w∈V-S P[w] = P[v]; P[w][w] = TRUE; // P[w] = P[v] + [w] }// if }// for }// ShortestPath_DIJ 二、每一对顶点之间的最短路径 方法一:每次以一个顶点为源点,重复执行迪杰斯特拉方法 方法二：Floyd 算法,求顶点对Vi,Vj的最短路径： (1)Vi,V0,Vj的路径长度与Vi,Vj比较，小者为从Vi到Vj的中间顶点序号不大于0的最短路径 (2) 加入顶点V1, 设Vi,……,V1和V1,……,Vj为 中间顶点序号不大于0的最短路径， 比较Vi,……,V1,……,Vj和Vi,V0,Vj， 小者为从Vi到Vj的中间顶点序号不大于1的最短路径 定义n阶方阵序列： 表示从Vi到Vj的中间顶点序号不大于k的最短路径的长, v0 v1 v2 6 4 11 3 2 (3)依次加入V2,V3,……,Vn-1, 共经过n次比较后，求得Vi到Vj的最短路径 void ShortestPath_FLOYD(Mgraph G, PathMa