资源描述：
《算法设计与分析第9讲 最短路径.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、贪心方法1单源最短路径问题路径：有向带权连通图，G=(V,E),w:E->R,P=v1-v2-…-vk具有权和，w(p)=∑i=1~k-1w(vi,vi+1)u和v间最短路径：δ(u,v)=minw(p),v1=u,vk=v为保证存在最短路径，假设所有权值为正。61251597108143uv2最优子结构特点IFu--v是最短，则x--y也是最短路径uxyv证明：cut-paste,反证法，如果x—y不是最短，则存在另一条路径x**y更短，那么u--x+x**y+y--v是一条比u--v更短的路径,从而与u--
2、v是最短路径矛盾。同时，还满足重叠子结构特点，因此可用动态规划。但我们还是用贪心方法3三角不等式对所有的顶点，u,v,x∈V,δ(u,v)<=δ(u,x)+δ(x,v)uxyδ(u,v)是最短路径，当然不会比u,x,y这条路径更长4单源最短路径问题给定源点s∈V,寻找最短路径δ(s,v),v为任意思路：1维持一个定点集合S,其中的估算最短距离已经解出。s是第一个点。2每一步，将V-S中估算距离最小的点加入S(贪心选择)3更新估算距离5Dijkstra算法Dijkstra(G,w,s)d(s)=0,d(V-s)=
3、∞,S=Null,Q=V//d估算距离whileQ=nulldou=min_extract(Q)S=S+{u}foreachv=Adj[u]ifd[v]>d[u]+w(u,v)//松弛操作thend[v]=d[u]+w(u,v)我们要证明最后的d[v],就是最短距离。6一个例子7正确性引理1每一步松弛操作前后，都保证d[v]>=δ(s,v)证明：归纳法。初始：d[s]=0,d[V-s]=∞,故满足。假设某次松弛操作v之前的都是满足的,而d[v]=d[u]+w(u,v)>=δ(s,u)+δ(u,v)>=δ(s,v
4、).8正确引理2假如s-----u-v是最短路径，如果d[u]=δ(s,u),那么松弛(u,v)后，d[v]=δ(s,v)证明：δ(s,v)＝δ(s,u)+w(u,v)=d[u]+w(u,v)=d[v]9正确性引理3到Dijkstra算法结束时，d[v]=δ(s,v)证明：假设在u之前，加入S的点，都满足了d[v]=δ(s,v).现在加入u。选取一条最短路径(s,u),y是第一次出S,x是前一点。P(s,y)=δ(s,v)(最优子结构).x满足d[x]=δ(s,x)（归纳假设），故在松弛x时，d[y]=δ(s,
5、y)(引理2).如u就是y，则归纳成功。如果u不是y,则因为y在外面，而现在加入u,说明d[u]δ(s,u]>δ(s,y)=d[y]矛盾sxyuS10复杂性分析跟最小生成树一个结构；Time=θ(V+Vtextract+Etdeckey)Q用不同的结构，时间有所区别textracttdeckeyTime数组θ(v)θ(1)θ(V2)最小堆θ(lgv)θ(lgv)θ(Elgv)Fib堆θ(lgv)θ(1)θ(E+Vlgv)11特例如果边的权值全部为1.则构成一个宽度优先访问算法。如果不采用
6、优先队列，用FIFO队列可以满足要求，（因为短的自然先处理）那么Time=θ(V+Vtextract+Etdeckey)那么T=(V+E)12
