数据结构拓扑排序和最短路径.ppt

最短路径问题 拓扑排序 某个源点到其余各点的最短路径 每一对顶点之间的最短路径 小结和作业 单源点的最短路径 Dijkstra算法 Dijkstra算法 Dijkstra算法 Dijkstra算法实现 Dijkstra算法实现 1）设置初始值： 2）从D中选择一个最小值，假设为D[k]，要求Vk 不在S中 3）修改不在S中的每个顶点u的最短路径值 若D[k]+G.arcs[k][u]D[u] 则D[u]=D[k]+G.arcs[k][u] V0和k之间存在弧 V0和k之间不存在弧 Dijkstra算法 S={V0} 4）重复2，3，直到所有的顶点都在S中 如何保存V0到V的路径？ 1、保存V0到V的路径上的顶点（即：不保存边和顶点之间的顺序） 2、存储结构：n×n的矩阵p Dijkstra算法 3、矩阵的第V行表示V0到V的路径上顶点 如果顶点W在路径上，则p[v][w]=TRUE 否则，p[v][w]=FALSE 初始： 如果V与顶点V0邻接，则p[v][V0]=TRUE，其它数矩阵元素的值都是FALSE。 当从V0到V的路径是经过V0到W的路径，然后，通过边W, V到达V，则p[v] =p[w]，p[v][v]=TRUE Dijkstra算法 Dijkstra算法 V0 100 10 10 5 50 V1 V2 V5 V4 60 V3 20 30 F F F F F F V0 V1 V2 V3 V4 V5 V0 V1 V2 V3 V4 V5 F F F F F F T F T F F F F F F F F F T F F F T F T F F F F T 选取V2后，V0到V3的路径经过V2 P[V3] = P[V2] P[V3][V3] = TRUE T F T F F F T F T T F F 图：带权的邻接矩阵路径：矩阵 距离：数组D S：数组final[]，如果final[v]=TRUE，则v在S中 void ShortestPath_DIJ(MGraph G, int v0, PathMatrix P, ShortestPathTable D){ for(v=0;vG.vexnum;++v){ final[v]=FALSE; //S中的顶点 D[v]=G.arcs[v0][v];//v0到v的路径的长度 for(w=0;wG.vexnum;++w) p[v][w]=FALSE; if(D[v]INFINITY){//V0的邻接点 p[v][v0]=TRUE; p[v][v]=TRUE; }//if }//for final[v0]=TRUE; ………… } void ShortestPath_DIJ(MGraph G, int v0, PathMatrix P, ShortestPathTable D){ //主循环，每次求得v0到某个顶点v的最短路径， //并将v加到S集中 for(i=1;iG.vexnum;++i){ min=INFINITY;//找余下顶点中的最短路径 for(w=0;wG.vexnum;++w){ if(!final[w]) if(D[w]min) {v=w; min=D[w]; } final[v]=TRUE;//v入选，即v0到v的路径最短 ………… } } Dijkstra算法实现 void ShortestPath_DIJ(MGraph G, int v0,PathMatrix P, ShortestPathTable D){ for(w=0;wG.vexnum;++w) { if(!final[w](min+G.arcs[v][w]D[w])){ D[w]=min+G.arcs[v][w];//修改距离 p[w]=p[v];//修改路径