数据结构图最短路径.pptx
6.7 最短路径用带权的有向图表示一个交通运输网，图中：顶点表示城市边表示城市间的交通联系权表示此线路的长度或沿此线路运输所花的时间或费用等问题：从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径最短路径l从某个源点到其余各顶点的最短路径51643208562301371732913长度最短路径8131921 20第1页/共14页 求从源点到其余各点的最短路径求从源点到其余各点的最短路径的算法的基本思想的算法的基本思想:依最短路径的长度递增的次序求得依最短路径的长度递增的次序求得各条路径各条路径源点源点v1其中，从源点到从源点到顶点顶点v的最短路径的最短路径是所有最短路径中长度最短者。v2第2页/共14页 在这条路径上，必定只含一条弧，并且这条弧的权值最小。下一条路径长度次短的最短路径最短路径的特点：路径长度最短的最短路径最短路径的特点：它只可能有两种情况：或者是直接从源点到该点(只含一条弧)；或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)。第3页/共14页其余最短路径的特点：再下一条路径长度次短的最短路径最短路径的特点:它可能有三种情况：或者是直接从源点到该点(只含一条弧)；或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)；或者是从源点经过顶点v2，再到达该顶点。它或者是直接从源点到该点(只含一条弧)；或者是从源点经过已求得最短路径的顶点，再到达该顶点。第4页/共14页求最短路径的迪杰斯特拉(Dijkstra)算法：设置辅助数组D，其中每个分量D k 表示 当前所求得的从源点到其余各顶点 k 的最短路径。一般情况下，D k=或者=+。第5页/共14页1）在所有从源点出发的弧中选取一条权值最小的弧，即为第一条最短路径。2）修改其它各顶点的D k值。假设求得最短路径的顶点为u，若若 Distu+G.arcsukDistk则将 D k 改为 D u+G.arcsuk。V0和k之间存在弧V0和k之间不存在弧其中的最小值即为最短路径的长度其中的最小值即为最短路径的长度。第6页/共14页1383032V2:813-133032V1:13-13302220V3:13-192220V4:19终点 从V0到各终点的最短路径及其长度V1V2V3V4V5V6Vj-2120V6:20516432085623013717329第7页/共14页课堂练习试利用DijkstraDijkstra算法求图中从顶点a a到其他各顶点间的最短路径，列表写出执行算法过程中各步的状态。第8页/共14页解答第9页/共14页弗洛伊德算法(Floyd)的基本思想是：从 vi 到 vj 的所有可能存在的路径中，选出一条长度最短的路径。求每一对顶点之间的最短路径求每一对顶点之间的最短路径第10页/共14页若存在，则存在路径vi,vj /路径中不含其它顶点若,存在，则存在路径vi,v1,vj /路径中所含顶点序号不大于1若vi,v2,v2,vj存在，则存在一条路径vi,v2,vj /路径中所含顶点序号不大于2 依次类推，则 vi 至 vj 的最短路径应是上述这些路径中，路径长度最小者。第11页/共14页例ACB2643110 4 116 0 23 0初始：路径：AB ACBA BCCA0 4 66 0 23 7 0加入V2：路径：AB ABCBA BCCA CAB0 4 116 0 23 7 0加入V1：路径：AB ACBA BCCA CAB0 4 65 0 23 7 0加入V3：路径：AB ABCBCA BCCA CAB第12页/共14页作业试利用DijkstraDijkstra算法求图中从顶点a a到其他各顶点间的最短路径，列表写出执行算法过程中各步的状态。15第13页/共14页感谢您的观看。第14页/共14页
