文档介绍：2016数据结构Datastructure讲授:、,从一个顶点到另一个顶点路径权值最小的路径,称为最短路径。(Source),路径的最后一个顶点称为终点(Destination)。【示例5-15】某交通网络由若干个城市和多条道路组成,从一个城市到另一个城市可能有多条道路,现有如下问题需要解决。①在指定城市到其它各城市之间均找出一条最短道路;现有如下问题需要解决②找出其它各城市到指定城市之间的一条最短道路③找出指定两个城市之间的一条最短道路;④找出任何两个城市之间的一条最短道路;交通网络可以用带权图表示:图中顶点表示城市,边表示两个城市之间的道路,边上的权值表示道路的长度。这样,交通网络所提出的4个问题就是带权图中求最短路径的问题。(1)单源最短路径问题在已知带权图G=(V,E)中,找出从某个源点s∈V到V中其余各顶点的最短路径。(2)单目标最短路径问题找出图中每一顶点v到某指定顶点u的最短路径。对无向图来说,该问题就是源点为u的单源最短路径问题;而对有向图来说,把图中的每条边反向后,该问题就是源点为u的单源最短路径问题。(3)单顶点对间最短路径问题对图中某对顶点u和v,找出从u到v的一条最短路径。该问题是源点为u的单源最短路径问题的子问题。(4)所有顶点对间最短路径问题对图中每对顶点u和v,,即多个单源最短路径问题的子问题。当然,也有专门用于解决此问题Floyd-Warshall算法。因此,后3个问题可由第(1)个问题来解决,下面来介绍单源最短路径问题的解决方法。荷兰计算机科学家迪杰斯特拉(Dijkstra)提出来一种按路径长度递增的顺序产生各顶点最短路径的算法。该算法要求图中边上的权值必须是非负实数。一、、迪杰斯特拉算法设G=(V,E)是含有n个顶点的带权图,s为源点,另设顶点集S和T=V-S,S用于存放已找到最短路径的顶点,T用于存放当前还未找到最短路径的顶点。,将其加入S中,重复上述过程,直到T中的顶点全部加入S或无通路为止。04132100106020501030图5-,需设置一个辅助向量D和P,D用来存放从源点s到V中每个顶点当前的最小权值(不妨称为估计),D的每个分量D[i](0≤i<n)表示当前从源点s到顶点vi的估计;P的分量P[i]用来存放从源点s到顶点vi最短路径的前驱顶点。需要注意的是,当有顶点加入S后,从源点s到T中各顶点的估计可能发生变化,因此需要修正D各元素的估计,称为重新估计。04132100106020501030图5-19有向网G11intD[N];//存放源点到V中顶点的最小权值intP[M];//①初始化:初始时S只包含源点s;T包含其它所有顶点;D[0]为从源点s到s的估计设为0,D[i]为从源点s到顶点vi的估计设为:若从源点s到顶点vi有边或弧,则D[i]为边(s,vi)或弧<s,vi>上的权值,否则为∞;P[i](1≤i<n)均为源点s。转向②。②求最短路径权值:取从源点s到T中所有顶点的最小估计Min{D[i]|vi∈T},设为D[j],将对应的顶点vj从T中去除加入S。转向③。③重新估计:顶点vj加入S后,对T中的每个顶点vk,从源点s到顶点vk的估计D[k]或者是原来的D[k];或者是经过S的路径(s,vj,vk),此时D[k]=D[j]+边(vj,vk)或弧<vj,vk>上的权值,这时vj是vk的前驱,用vj修正P[k]。转向④。④若T为空,算法结束,此时,S中的顶点序列便是按最短路径递增顺序产生的顶点序列,向量D中各元素的值就是从源点s到V中各顶点最短路径的权值,向量P记录了从源点s到V中各顶点最短路径;否则,转向②。