问题5： 在本章中介绍的算法基本思路 是一样的，那是什么？ Bellman-Ford算法、DAG算法、Dijkstra算法 松弛+有序的松弛
Bellman-Ford算法、DAG算法、Dijkstra算法 松弛+有序的松弛
问题6： Relax到底在干什么？ 为什么它会是最短路算法的核心？
从这个案例中，我们能够得到的启发： 令u.d是源点s到节点u的最短距离的预测，初始定义u.d=∞. u.d是&(s,u的上界，但不紧致 若节点u有一条有向边射入节点v,且此时u.d和v.d分别为5和9 v.d是否可以被紧致到一个更小的上界，比如7？
从这个案例中，我们能够得到的启发： 令u.d是源点s到节点u的最短距离的预测,初始定义u.d=∞. 若节点u有一条有向边射入节点v,且此时u.d和v.d分别为5和9 v.d是否可以被紧致到一个更小的上界，比如7? u.d是&(s,u)的上界，但不紧致
Lemma 24.10(Triangle inequality) Let G =(V,E)be a weighted,directed graph with weight function w E-R and source vertex s.Then,for all edges (u,v)EE,we have 8(s,v)≤6(s,u)+w(u,v). W(u,) &(S,U) &(s,)
s u v &(s,u) &(s,v) w(u,v)
2 RELAX(u,v,w) 1 if v.d u.d+w(u,v) 2 v.d u.d+w(u,v) RELAX(u,v,W) 3 V.π=u 7一定比9更 u 靠谱 当我们有u.d这么一个预估值后，V.d这个预估值必须小于u.d+w(u,), 否则必须修正v.d为u.d+w(u,) 修正后的v.d未必就是最终的解&(S,V),但一定是一个更紧致的上界
s u v 当我们有u.d这么一个预估值后，v.d这个预估值必须小于u.d+w(u,v), 否则必须修正v.d为u.d+w(u,v) 修正后的v.d未必就是最终的解&(s,v)，但一定是一个更紧致的上界 u.d v.d 7一定比9更 靠谱