高级图算法.pptVIP

现在考虑当出队列时，顶点v的颜色变化情况： 如果是v白色的，由于紧邻顶点那么由BFS算法第13行得d[v] = d[u] + 1 ； 如果v是深灰色的，那么它已经先于u从队列中移走，由推论8.1，有d[v]≤d[u]. ； 如果v是灰色的，那么它是在某个顶点w出队列时被标记为灰色，其中w为从队列Q中移出得比u更早的一个顶点，且有d[v] = d[w] + 1 。由推论8.1，有d[w] ≤ d[u]，所以有d[v] ≤d[u] + 1 终止步：当KruskalMST算法结束时，所有被加到中的边都在最小生成树中，所以第9行返回的必为最小生成树。 当u被加入到S时，由于d[x] = δ(s,x) ，而y是路径p中紧挨着顶点x的点，根据最短路径的收敛性质，我们有d[y] = δ(s,y) 。 现在，为了得到一个与假设d[u]≠δ(s, u)矛盾的结果，我们只须证明d[u]=δ(s, u) 。因为在从s到u的最短路径中，y在u之前出现，并且所有边非负，我们有δ(s, y) ≤δ(s, u), ，并且根据最短路径的上界性质δ(s, u) ≤ d[u]. ，我们有 d[y] = δ(s, y) ≤δ(s, u) ≤ d[u]. * BellmanFord(G, w, s) 1 InitializeSingleSource(G, s) 2 for i ← 1 to |V| - 1 do 3 for each edge (u, v)∈ E do 4 Relax(u, v, w) 5 for each edge (u, v) ∈ E do 6 if d[v] d[u] + w(u, v) then return False 7 return True The running time O(|V||E|) O(|V||E|) O(|E|) Θ(|V|) * An example 0 ∞ ∞ ∞ ∞ 5 -2 6 7 8 7 9 2 -3 -4 BellmanFord(G, w, s) 1 InitializeSingleSource(G, s) 2 for i ← 1 to |V| - 1 do 3 for each edge (u, v)∈ E do 4 Relax(u, v, w) 5 for each edge (u, v) ∈ E do 6 if d[v] d[u] + w(u, v) then return False 7 return True 5 -2 6 7 8 7 9 2 -3 -4 s t x y z s t x y z * 0 6 7 ∞ ∞ 5 -2 6 7 8 7 9 2 -3 -5 0 ∞ ∞ ∞ ∞ 5 -2 6 7 8 7 9 2 -3 -4 s t x y z y z s t x BellmanFord(G, w, s) 1 InitializeSingleSource(G, s) 2 for i ← 1 to |V| - 1 do 3 for each edge (u, v)∈ E do 4 Relax(u, v, w) 5 for each edge (u, v) ∈ E do 6 if d[v] d[u] + w(u, v) then return False 7 return True * 0 6 7 4 2 5 -2 6 7 8 7 9 2 -3 -4 0 6 7 ∞ ∞ 5 -2 6 7 8 7 9 2 -3 -5 y z s t x z y s t x BellmanFord(G, w, s) 1 InitializeSingleSource(G, s) 2 for i ← 1 to |V| - 1 do 3 for each edge (u, v)∈ E do 4 Relax(u, v, w) 5 for each edge (u, v) ∈ E do 6 if d[v] d[u] + w(u, v) then return False 7 return True * 0 2 7 4 2 5 -2 6 7 8 7 9 2 -3 -4 0 6 7 4 2 5 -2 6 7 8 7 9 2 -3 -4 z y s t x z y t x s BellmanFord(G, w, s) 1 InitializeSingleSource(G, s) 2 for i ← 1 to |V| - 1 do 3 for each edge (u, v)∈ E do 4 Relax(u