算法设计与分析 课件 第七章 分支限界 7.3.2 单源最短路径问题

计算机算法设计与分析第7章分支限界法7.3.2单源最短路径问题给定带权有向图G=(V,E),其中每条边的权是非负实数.另外,还给定V中的一个顶点,称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路径的长度是指路径上各边权之和。这个问题通常称为单源最短路径问题。单源最短路径问题如图所示的有向图G，每一条边都有一个非负权值，求源点S到图中各个结点之间的最短路径。算法分析采用优先队列式分支限界法求解单源最短路径问题，可以构建一个基于结点优先级的小根堆来存放活动结点表：结点的优先级=源点到该结点的当前路径长度初始时源点到其余个结点之间距离长度dist[i]设置为无穷大，当然源点本身的dist[S]=0，并将源点S加入优先队列（小根堆）。图的邻接矩阵存储到二维数组edge内。算法分析从小根堆中取出堆顶元作为当前扩展结点i，并依次检查与结点i相邻结点j是否满足下列条件：dist[i]+edge[i][j]<dist[j]则更新结点j的优先级dist[j]=dist[i]+edge[i][j]，并将j结点加入小根堆（优先队列）。否则被舍去处理。重复上述过程，直到小根堆(优先队列)为空为止。Sijdist[i]edge[i][j]dist[j]实例（1）开始时小根堆只有源点S，取堆顶元S作为扩展结点，与S相邻的结点A，B，C，都满足更新其优先级条件，所以更新A、B、C的优先级，将A、B、C结点加入小根堆，结点加入小根堆的过程中会重新调整建堆。dist[A]=dist[S]+edge[S][A]=2dist[B]=dist[S]+edge[S][B]=3dist[C]=dist[S]+edge[S][C]=4此时的解空间树如下图所示。SABC实例（2）取小根堆的堆顶元为A结点，与A相邻的B、E、F结点：dist[A]+edge[A][B]>dist[B]，剪枝由A扩展的B结点。dist[E]=dist[A]+edge[A][E]=2+2=4dist[F]=dist[A]+edge[A][F]=2+7=9更新结点E,F的优先级并将其加入堆、重新调整建堆。此时的解空间树如下图所示。ABCBCEF实例（3）此时，小根堆（优先队列）的堆顶元为优先级最小的结点B，与B相邻的C、D、E，只有结点D满足优先级更新条件而加入到堆，加入堆的过程中会重新调整建堆。dist[D]=dist[B]+edge[B][D]=3+2=5由B扩展的结点C、E被剪枝舍去。此时的解空间树如下图所示。BCEFCDEF实例（4）此时，堆顶元为优先级最小的结点C，取堆顶元C,与C相邻的结点D不满足优先级更新条件，剪枝由C扩展的结点D。此时的解空间树如下图所示。CDEFEDF实例（5）此时，堆顶元为结点E，取堆顶元E,与E相邻的D、H，E扩展的结点D因不满足优先级更新条件被剪枝舍去，dist[H]=dist[E]+edge[E][H]=4+3=7结点H加入堆。此时的解空间树如下图所示。EDFDFH实例（6）取堆顶元结点D，与D相邻的结点I和H，因结点H不满足优先级更新条件而被舍去，dist[I]=dist[D]+edge[D][H]=5+1=6结点I更新优先级并加入堆。此时的解空间树如下图所示。DFHIFH实例（7）此时的堆顶元为结点I，取堆顶元I，与I相邻的H、T,因I扩展的结点H不满足优先级更新条件被剪枝舍去dist[T]=dist[I]+edge[I][T]=6+2=8更新结点T优先级并加入堆。此时的解空间树如图所示。IFHHFT实例（8）此时，结点H具有最高优先级成为当前堆顶元，取堆顶元H,与H相邻的G、T，由H扩展的结点T不满足优先级更新条件被剪枝舍去;dist[G]=dist[H]+edge[H][G]=7+2=9结点G加入堆。此时的解空间树如下图所示。HFTTFG实例（9）此时，结点T为小根堆的堆顶元。此时，若问题是求解源点S到终点T的的最短路径，则已得到问题的解，可以提前结束循环。若需要求源点到图中所有结点的最短路径长度，则还需要继续执行，直到堆（优先队列）为空才结束循环。这时取堆顶元T,因T没有出度边的邻结点，出堆后无操作。此时G成为当前堆顶元，扩展的结点T，且不满足约束条件被剪枝舍去。此时的解空间树如下图所示。TFGGFF实例（10）到了此时，优先队