PPT《图的基本概念 图的存储结构 图的遍历 最小生成树 最短路径 ...》

图的基本概念 图的存储结构 图的遍历 最小生成树 最短路径 拓扑排序 关键路径 最短路径 (Shortest Path) 最短路径问题:如果从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条,如何找到一条路径,使得沿此路径各边上的权值总和达到最小.

问题解法单源最短路径 ― Dijkstra算法任意顶点对之间的最短路径 ― Floyd算法 单源最短路径问题 问题的提出: 给定一个带权有向图G与源点v,求从v到G中其它顶点的最短路径.限定各边上的权值大于或等于0.为求得这些最短路径,Dijkstra提出按路径长度的递增次序,逐步产生最短路径的算法.首先求出长度最短的一条最短路径,再参照它求出长度次短的一条最短路径,依次类推,直到从顶点v到其它各顶点的最短路径全部求出为止.举例说明 Dijkstra逐步求解的过程 算法的基本思想 设置并逐步扩充一个集合S,存放已求出的最短路径的顶点,则尚未确定最短路径的顶点集合是V-S, 为了直观起见,我们设想S中顶点均被涂成红色,V-S中的顶点均被涂成蓝色.算法初始化时,红点集中仅有一个源点,以后每一步都是按最短路径长度递增的顺序,逐个地把蓝点集中的顶点涂成红色后,加入到红点集中. 算法粗框:while ( S 中的红点数 < n ) 在当前蓝点集中选择一个最短路径长度最短的 蓝点扩充到蓝点集中;

那么,如何在蓝点集中选择一个最短路径长度最短的蓝点呢? 注意:这种蓝点所对应的最短路径上,除终点外,其余顶点都是红点.为此,对于图中每一个顶点 i ,都必须记住从v 到i 、且中间只经过红点的最短路径的长度,并将此长度记作 i 的距离值. 开始时,红点集只有一个源点v,初始蓝点集中的蓝点j的距离值D[j]均为有向边上的权值. 用数组D(n)来存放n个顶点的距离值.若当前蓝点集中具有最小距离值的蓝点是k,则其距离值D(k)是k的最短路径长度,并且k是蓝点集中最短路径长度最短的顶点. 证明1: (距离值D(k)是k的最短路径长度) 若D(k)不是k的最短路径长度,则必存在另外一条从源点v到k的路径P,其长度小于D(k).由距离值的定义可知,路径P上必然包含一个或多个蓝点作为中间点.假设从源点沿P向前第一次碰到的蓝点是x,则P上从源点v到x的这一段路径的长度,显然不小于x的距离值D(x).而P上从x到终点k所经过的边上,其权值均为非负实数,所以D(x)=D(k).由此可知蓝点集中任意顶点i的最短路径长度都不会小于k的最短路径长度D(k). 扩充红点集的方法:每一步只要在当前蓝点集中选择一个具有最小的距离值的蓝点k扩充到红点集合中,k被涂成红色之后,剩余的蓝点的距离值可能由于增加了新红点k而发生变化(即减少).因此必须调整当前蓝点集中各蓝点的距离值.算法框架: S = {v};

置初始蓝点集中各蓝点的距离值;

while ( S中红点数 < n ) { 在当前蓝点集中选择距离值最小的顶点k;

S = S + {k}将k涂成红色加入红点集 */ 调整剩余蓝点的距离值;

} 如何调整剩余蓝点的距离值呢? 若新红点k加入红点集S后,使得某个蓝点j的距离值D(j)减少,则必定是由于存在一条从源点v途径新红点k最终到达蓝点j且中间只经过红点的、新的最短路径Pvkj,它的长度小于从源点v到达j且中间只经过老红点(即步包含k)的原最短路径Pvj的长度D(j).由于Pvkj是一条中间只经过红点的最短路径,所以,它的前一段从v到k的路径必定是k的最短路径,其长度为D(k);

它的后一段从k到j的路径Pkj只可能有两种情形:其一是由k经过边直达蓝点j;

其二是从k出发再经过S中若干老红点后到达j. 用反正法证明后一种情形是不可能的. 假设从源点v出发,经过红点k、老红点x,最后到达蓝点j的新最短路径Pvkxj的长度小于原D(j).因为x比k先加入红点集S,故D(x)