问题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中的“修正”到底在 干什么？