资源描述：
《数据结构.第7章.图.4.最短路径.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、数据结构DataStructures张凯计算机学院软件工程系2011年3月12日图的连通性问题第7章图图的定义和术语图的存储结构图的遍历有向无环图及其应用最短路径最短路径问题§7.6最短路径典型用途：交通问题。如：城市A到城市B有多条线路，但每条线路的交通费（或所需时间）不同，那么，如何选择一条线路，使总费用（或总时间）最少？问题抽象：在带权有向图中A点（源点）到达B点（终点）的多条路径中，寻找一条各边权值之和最小的路径，即最短路径。（注：最短路径与最小生成树不同，路径上不一定包含n个顶点）最短路径问题§7.6最短路径一顶点到其余各顶点两种常见的最短路
2、径问题：一、单源最短路径—用Dijkstra（迪杰斯特拉）算法二、所有顶点间的最短路径—用Floyd（弗洛伊德）算法任意两顶点之间单源最短路径(Dijkstra算法)§7.6最短路径目的：设一有向图G=（V,E），已知各边的权值，以某指定点v0为源点，求从v0到图的其余各点的最短路径。限定各边上的权值大于或等于0。源点从F→A的路径有4条：①F→A：24②F→B→A：5＋18=23③F→B→C→A：5+7+9=21④F→D→C→A：25+12+9=36又：从F→B的最短路径是哪条？从F→C的最短路径是哪条？v0(v0,v1)10源点终点最短路径路径长度
3、(v0,v1,v2)(v0,v3,v2)(v0,v3)30v1v2v3v4100(v0,v4)(v0,v3,v4)(v0,v3,v2,v4)例：60509070讨论：计算机如何自动求出这些最短路径？(v0,v1,v2,v4)60V0V1V2V3V4V0∞10∞30100V1∞∞50∞∞V2∞∞∞5010V3∞∞20∞60V4∞∞20∞∞V0V2V1V4V3101003010506020单源最短路径(Dijkstra算法)§7.6最短路径V0V1V2V3V4V0∞10∞30100V1∞∞50∞∞V2∞∞∞5010V3∞∞20∞60V4∞∞20∞∞V0V2
4、V1V4V3101003010506020思考：单源最短路径(Dijkstra算法)§7.6最短路径算法思想：先找出从源点v0到各终点vk的直达路径(v0,vk),即通过一条弧到达的路径。从这些路径中找出一条长度最短的路径(v0,u),然后对其余各条路径进行适当调整：若在图中存在弧(u,vk)，且(v0,u)+(u,vk)<(v0,vk),则以路径(v0,u,vk)代替(v0,vk)。在调整后的各条路径中，再找长度最短的路径，依此类推。总之，按路径“长度”递增的次序来逐步产生最短路径单源最短路径(Dijkstra算法)§7.6最短路径给定带权有向图G和
5、源点v,求从v到G中其余各顶点的最短路径。V5V0V2V4V1V31003010601020505V0V2V4V3V5V0始点终点D[i]最短路径V1V2V3V4V5∞10∞30100∞10∞30100∞106030100∞106030100∞105030100(V0,V2)(V0,V4)(V0,V5)(V0,V2)(V0,V4)(V0,V5)(V0,V2)(V0,V2,V3)(V0,V4)(V0,V5)(V0,V2)(V0,V2,V3)(V0,V4)(V0,V5)(V0,V2)(V0,V4,V3)(V0,V4)(V0,V5)∞10503090(V0,
6、V2)(V0,V4,V3)(V0,V4)(V0,V4,V5)∞10503090(V0,V2)(V0,V4,V3)(V0,V4)(V0,V4,V5)∞10503060(V0,V2)(V0,V4,V3)(V0,V4)(V0,V4,V3,V5)∞10503060(V0,V2)(V0,V4,V3)(V0,V4)(V0,V4,V3,V5)(v0,v2)+(v2,v3)<(v0,v3)终点从v0到各终点的dist值和最短路径v1v2v3v4v5vjS之外的当前最短路径之顶点60{v0,v2,v3}50{v0,v4,v3}30{v0,v4}90{v0,v4,v5}6
7、0{v0,v4,v3,v5}s{v0,v2}{v0,v2,v4}{v0,v2,v4,v3}{v0,v2,v4,v3,v5}10{v0,v2}∞30{v0,v4}100{v0,v5}∞∞∞∞v2v4v3v5100{v0,v5}012345dist[w]012345与最小生成树的不同点：路径是累加的！10{v0,v2}50{v0,v4,v3}30{v0,v4}V5V0V2V4V1V31003010601020505所有顶点对之间的最短路径(Floyd算法)§7.6最短路径问题描述：已知一个各边权值均大于0的带权有向图，对每对顶点vi≠vj，要求求出每一对顶
8、点之间的最短路径和最短路径长度。解决方案：1.每次以一个顶点为源点，重复执行迪杰斯特拉算法n次
