数据结构（Java语言描述）（第2版）课件 5.6 最短路径

数据结构主讲人：杨丹常州信息职业技术学院5.6最短路径在一个图中，若从一个顶点到另外一个顶点存在路径，路径长度就是一条路径上所经过的边的数目。图中从一个顶点到另外一个顶点可能存在多条路径，路径长度最短的那条路径叫做最短路径，其路径长度称为最短路径长度或最短距离。引言IntroductionPart01带权图的最短路径在一个带权图中，若从一个顶点到另外一个顶点存在一条路径，则称该路径上所经过边的权值之和为该路径上的带权路径长度。带权图中从一个顶点到另外一个顶点可能存在着许多条路径，带权路径长度值最小的那条路径称为最短路径，其带权路径长度叫做最短路径长度或最短距离。带权图可以分为有向图和无向图。如果把无向带权图的每一条边(u,v)都定义为弧<u,v>和弧<v,u>，则无向带权图也就可以转换为有向带权图。不失一般性，这里讨论有向带权图的最短路径问题。最短路径说明带权图的最短路径带权图的最短路径5示例示例左图所示的有向带权图从顶点A到顶点D有四条路径，分别是路径(A,D)，其带权路径长度为30；路径(A,C,F,D)，其带权路径长度为22；路径(A,C,F,E,D)，其带权路径长度为34；路径(A,C,B,E,D)，其带权路径长度为32。路径(A,C,F,D)称为最短路径，其带权路径长度22为最短距离。Part02单源最短路径设有一个有向带权图G=(V,E)，其中每条边的权是一个非负实数，给定V中的一个顶点，称为源点（Source），求从源点到所有其他各顶点的最短路径长度（长度是指路径上各边权之和）的问题称为单源最短路径问题（SingleSourceShortestPaths）。

对于有向带权图从一个确定顶点（称为源点）到其余各顶点的最短路径问题，迪杰斯特拉（Dijkstra）提出了一个按路径长度递增的顺序逐步产生最短路径的构造方法。单源最短路径单源最短路径基本思想迪杰斯特拉（Dijkstra）算法将顶点集V分成S（开始只包含源点s，S包含的点都是已经计算出最短路径的点）和V-S集合（V-S包含那些未确定最短路径的点）；如此反复，直到V-S变空集为止。从V-S中选取这样一个顶点w：满足经过S集合中任意顶点v到w的路径最短，即满足{v到w的路径}最小的那个w。其中v属于S，w属于V-S。将w加入S，并从V-S中移除w；Dijkstra算法步骤【例】用迪杰斯特拉（Dijkstra）算法求下图G中顶点A到其余各顶点的最短距离。图GDijkstra算法步骤Dijkstra算法步骤Dijkstra算法步骤源点中间顶点终点路径长度ACB20A

C5AC,FD22AC,BE28ACF12表

源点到其他各顶点的最短路径【例】用迪杰斯特拉（Dijkstra）算法求下图G中顶点A到其余各顶点的最短距离。Dijkstra算法实现distance[]用于存放源点到其余顶点的最短距离数值path[]表示从源点v到其余顶点的最短路径上到达目标顶点的前一个顶点boolean类型数组selected，selected[i](i=0,1,…n-1)用来标记是否已经确定源点v到第i