计算机算法基础 第2版 课件 第10章 单源最短路径.pptx

1第10章单源最短路径单源最短路径问题简介 2Dijkstra算法 3Ballman-Ford算法 14

21.单源最短路径问题简介问题定义：在给定的加权有向图G(V,E)中，取一顶点s为源点，计算从源点s到其他每个点v的最短路径p(s,v)，v?V，以及它的加权长度。最短路径的长度记为?(s,v)。主要算法：Dijkstra算法和Ballman-Ford算法都采用贪心法策略，包括初始化和循环部分。初始化置d(v)=?，v?V–{s}，置d(s)=0。d(v)含义是，到目前为止，能找到的从s到v的路径中最短的一条长度。循环部分，每一轮都会有至少一个新顶点的最短路径被确定下来。这样，在n轮之后，所有顶点的最短距离就产生了。（有些学者把Ballman-Ford算法归为动态规划。）

32.Dijkstra算法Dijkstra算法要求图G(V,E)中边的权值是非负实数。Dijkstra算法与Prim算法几乎完全一样。Dijkstra算法构造一棵最短路径树T，而Prim算法是构造MST。Dijkstra算法既适用于有向图又适用于无向图。Dijkstra算法简介 分为两部分，初始化部分和循环部分。(1)初始化部分(和Prim算法完全一样，但d(v)的含义不同):foreachv?V d(v)?? ?(v)?nil //点v的父亲endford(s)?0这里，d(v)表示从源点s到v的暂时距离，即目前找到的最短距离。在Prim算法中，d(v)表示的是，点v与当前已形成的树T的最短距离。

4Dijkstra算法简介(继续1)(2) 循环部分：循环前，树T是空集。以d(v)为关键字，用优先队列Q把所有树外的顶点组织起来。一共循环n次，每次循环做两件事：(2,1)找出当前树T以外的顶点中有最小d(u)的顶点u。? 和Prim算法完全一样，如果?(u)=h，那么，Dijkstra算法把边 (h,u)加到树T中，并且把u从Q中删除，修复Q。因为d(s)=0?，循环第一轮必定选取源点s。因为?(s)=nil，第一轮只把点s加到T里，没有边加入T。(2,2)逐个检查点u的还在树外的每个邻居v，即v?Adj(u)，v?Q。点u成了树中的点，为邻居v提供一条新路径，长为d(u)+w(u,v)。如果d(u)+w(u,v)d(v)，则d(v)更新为d(v)?d(u)+w(u,v)。(伪码见下页)

5Dijkstra算法简介(继续2)foreachv?Adj(u) ifv?Qandd(u)+w(u,v)d(v) then d(v)?d(u)+w(u,v) ?(v)?u endifendfor这一部分的伪码几乎和Prim相同。只要作如下改动就变成Prim算法了。把d(u)+w(u,v)d(v) 改为w(u,v)d(v),和把d(v)?d(u)+w(u,v) 改为d(v)?w(u,v)，也就是把”d(u)+“去掉， 就变成Prim算法了。(完整的Dijkstra算法的伪码见下页)

6SSSP-Dijkstra(G(V,E),s) //SSSP–SingleSourceShortestPath1 foreachv?V2 d(v)??3 ?(v)?nil4 endford(s)?06 V(A)?? //A是树T的边集合，V(A)是与A中边关联的顶点集合7 A?? //初始，树T的边集合为空8 Q?V //所有树外的顶点组织为Q9 whileQ??10 u?Extract-Min(Q) //从Q中剥离最小d(u)，修复Q11 A?A?{(?(u),u)} //如?(u)=nil，A不变12 V(A)?V(A)?{u}13 foreachv?Adj(u)14 ifv?Qandd(u)+w(u,v)d(v) 15 then d(v)?d(u)+w(u,v)16 ?(v)?u17 endifendforendwhile18 returnT(V(A),A) //最短路径树19 End把14行和15行中的d(u)+去掉就变成Prim算法了。

7例10.1 用Dijkstra算法找出下图中以顶点s为源点的最短路径树。1243852abscde1310