计算机问题求解一论题3-8 单源最短通路算法 2018年10月30日
计算机问题求解 – 论题3-8 - 单源最短通路算法 2018年10月30日
什么是最短通路问题: In a shortest-paths problem,we are given a weighted,directed graph G=(V,E),with weight function w:ER mapping edges to real-valued weights.The weight w(p)of path p=(vo.v1...v)is the sum of the weights of its constituent edges: 问题1: k w(p)=w(-1,). 输入是什么?输出是 i=1 什么? We define the shortest-path weight 8(u,v)from u to v by min()ithere isa pathfrom o otherwise A shortest path from vertex u to vertex v is then defined as any path p with weight w(p)=8u,)
什么是最短通路问题?
问题2 单源最短略问题的解必定是一棵树? A shortest-paths tree rooted at s is a directed subgraph G'=(V',E), where V'C V and E'C E,such that 1.V'is the set of vertices reachable from s in G, 2.G'forms a rooted tree with root s,and 3.for all vV,the unique simple path froms to v in G'is a shortest path froms to v in G. 由.T决定的 Vπ={v∈V:w.π≠NTL}U{s}· 最短路径树: E元={v.π,v)∈E:v∈Vπ-{s}
由.π决定的 最短路径树:
单源最短路问题具有最佳子结构性 Lemma 24.1 (Subpaths of shortest paths are shortest paths) Given a weighted,directed graph G=(V.E)with weight function w:E->R, let p =(vo,v1,....vk)be a shortest path from vertex vo to vertex vk and,for any i and j such that0≤i≤j≤k,let Pij=(i,vi+l,,vi)be the subpath of p from vertex vi to vertex vj.Then,Pij is a shortest path from vi to vj. Proof If we decompose path p into vv,then we have that w(p)=w(Poi)+w(Pij)+w(pik).Now,assume that there is a path p;from vi to with weight w(p(.Then,is a path from v to vk whose weight w(poi)+w(p)+w(pjk)is less than w(p),which contradicts the assumption that p is a shortest path from vo to vk
单源最短路问题具有最佳子结构性
S 问题3: 简单的greedy策略不能正确解决最短通路 问题!为什么?
s 2 6 1 7 v 问题3: 简单的greedy策略不能正确解决最短通路 问题! 为什么?
问题4: 具有负值权的回路对于单源 最短通路问题的解有什么影 响?非负值权的回路呢?
问题5: 在本章中介绍的算法基本 思路是一样的,那是什么?
预估”与“修正” INITIALIZE-SINGLE-SOURCE(G,S) 1 for each vertex v G.V 2 3 v.d=·. ).π=NIL RELAX(u,v,w) 4s.d=0 -ifv.d>u.d+w(u,v) 2 '>v.d u.d+w(u.v) 3 V.π=2u 2 ⑤ (6 RLAX(u.V) RELAX(u.v.Wv) ⑦ ⑤ 2 (a) (b)
“预估”与“修正
6 (a) (b (c) BELLMAN-FORD(G,w,s) 6 1 INITIALIZE-SINGLE-SOURCE(G,S) 2 for i 1to |G.V]-1 3 for each edge (u.v)G.E (d) (e) 遍历顺序 RELAX(u,v,w) 5 for each edge (u,v)G.E (t,x),(1,y),(亿,z,(x,t),y,x),y,z,(3,x),(3,S),(s,1,(s,y)6 if v.d>u.d+w(u,v) 7 return FALSE 8 return TRUE
遍历顺序
问题6: Relax中的“修正”到底在 干什么?