Scalers点评：：成长会的算法小组已经启动，这是第9周的学习笔记。
写在前面的话：Algorithms + Data Structures = Programs。程序的运行效率很大程度上取决于程序所采用的算法的性能。如果你想提高自己的编程能力，对程序的运行效率有追求，那么快加入和我们一起学习算法吧。算法小组是成长会内部小组，如果你想和我们一起学习算法，你需要是成长会成员，并且完成相关进群任务，欢迎做完入群任务后发给[S157]激流。
本周学习情况
本周（20160418-20160501）学习[MITOPENCOURSE]上的6.006的第17个和第18个lecture。这两个lecture还是主要讲最短路径，介绍了Bellman-Ford算法。
Shortest Paths I
最短路径 I
Shortest Paths are an application of dynamic programming and greedy algorithms.
最短路径法是动态规划和贪心算法的应用。
Paths 路径
consider digraph G = (V,E) with edge weights given by function w；E -> IR
前提，有加权的有向图 G =(V,E)，已知边的权重，权重用函数w表示，权重是每条边上的一个实数
path p=v1 -> v_2 -> .. -> v_k has weight w(p)= ∑ w(v_i,v_(i+1)) (和下 i=1;和上 k-1)
图的路径 p = v_1 -> v_2 ->.. ->v_k （directed edge有向边)路径的总权值等于路径上各边的权值的总和
Example:
Shortest Path from u to v is a path of minimum possible weight from u to v
u 点到 b 点的最短路径,路径的总权值尽可能地小
Shortest-Path weight from u to v is δ(u,v)=min{ w(p): p (path) from u to v}
从u到v的最短路径的权值是
δ(u,v) = min{ w(p): p (path) from u to v} = ∞ if no path from u to vminmum -> infimum 下确界（指对于一个集合的最大的下界）
when do shortest paths not exist?什么时候最短路径不存在？
Negtive edge weights （负权的边）=> some shortest paths may not exist:as long as there is a negtive weight cycle reachable from u to v 只要是从u到v的路径中，经过了一个负环，便不存在最短路径 δ(u,v) = -∞
it’s ∞ if no path from u to v 如果u 和 v之间没有路径时，我们设它为无穷大
Optimal Substructure 最优子结构
a subpath of a shortest path is a shortest path
最短路径的人任意子路径也是一条最短路径
Proof
Cut & Paste
contradiction
Triangle inequality:三角不等式：
for all vertices u,v, x ∈ V, δ(u,v)<=δ(u,x)+δ(x,v)
你有任意三个顶点，从u到v的最短路径，最大不超过u到x的最短路径加上x到v的最短路径
Proof:
by picture
Single-source shortest paths problem 单源最短路径问题
from given source vertex s ∈ V find shortest path weights δ(s,v) for all v ∈ V
从源顶点到达所有的点的最短路径（解决A到B最短路径的最优算法不会比这个问题更简单）
Today: Assume w(u,v)>0 u ∈ V v ∈ V 假设所有的边都是非负的，
=> shortest path exist provided paths exist 只要路径存在，最短路径则存在
=> δ(u,v) > -∞ 总是大于负无穷
算法思想 greedy 贪心算法
maintain set S of vertices whose shortest path distance from s S known (s ∈ S) 估算源点到每个点的距离（权值），估算距离已经是最短距离的顶点集合， 作为不变量
at each step add to S the vertx v ∈ V-S whose distance estimated is minimum ，每一步，在V-S的集合中，把离s的距离最短的点 v ，添加到S。
update distance estimates of vertices adjacent to v
Dijkastra algorithm Dijkastra 算法
d[x] = distance estimate from s to x = δ(s,x) when x ∈ S 输出
d[s] <- 0 for each v ∈ V {s} do d[v] <- ∞ S <- φ Q <- V //(priority queue,keyed on d) //initialization while Q ≠ φ do u <- Extract Min(Q) S <- S ∪ {u} for each v ∈ Adj{u} do if d[v] > d[u]+w(u,v) //d[u]=δ(s,u) then d[v]<-d[u]+w(u,v)//降键值的操作implicit decrease key //relaxation step 松弛Example
Q A B C D E 0 ∞ ∞ ∞ ∞ / 103 ∞ ∞ 7 / 115 7 11/ / 9shortest path tree 最短路径树= for each vertex in your graph last edge(u,v) relaxed
Correctness I
Invariant d[v] >= δ(s,v) for all v ∈ V holds after intialization & any sequence of relaxzationProof：Induction
Initially d[s] = 0 & d[v] = ∞ Vv ≠ s
>= δ(s,s) = 0 & δ(s,v) <= ∞
反证法 Suppose for contradiction that
invariant is violated
Condier first violation
d[v] < δ(s,v)
caused by relaxation
d[v] <- d[u] + w(u,v) < δ(s,v)
d[u]+w(u,v) >= δ(s,u)+w(u,v) >= δ(s,u)+δ(u,v) >= δ(s,v) XXX
Correctness lemma
Suppose s -> ...->u -> v is a shortest path If d[u] = δ(s,u) & we relax edge (u,v) then d[v] = δ(s,v) after relaxationProof
δ(s,v) = w(s->..->u)+w(u,v) = δ(s,u) + w(u,v) Correctness I => d[v] >= δ(s,v) Either d[v] = δ(s,v) before relaxation =>done or d[v] > δ(s,v) before relaxation δ(s,v)= d[u]+ w(u,v) => we relax & set d[v] <- d[u]+w(u,v) = δ(s,v)Correctness II:
when Dijkstra terminates, d[v] = δ(s,v) for all v ∈ VProof:
d[v] doesn't change once v is added to S => suffices to show d[v] = δ(s,v) when v is added to S Suppose for contradiction that u is the first vetex about to be added to S for which d[u] ≠ δ(s,u) => d[u] > δ(s,u) (by Correctness I) Let p be a shortest path from s to u=> w(p) = δ(s,u) Consider first edge (x, y) where p exits S First violation => d[x] = δ(s,x) when we added x to S we relaxed edged (x,y) So by correctness lemma d[y] = δ(s,y) <= δ(s,u) d[y] >= d[u] ContradictionTime = |V|T_ExtractMin+|E|T_DecreaseKey
Array => O(v^2)
Binary heap => O((v+E)lgV)
Fibanacci heap => O(E+VlgV)
Breadth first search 广度优先搜索(BFS)
Unweighted graphs w(u,v)=1 u,v ∈ V use FIFO queue instead of priority queue relax if d[v] = ∞ then d[v] <- d[u]+1 add to queue(Q,v)Time O(V+E)
最短路径算法：Bellman和差分约束系统
Dijkastra algorithm solves
single-source shortest paths
in O(E+VlgV) time
if w(u,v) >= 0 for all(u,v) ∈ E
Shortest Paths II
Recall
If G has a neg-weight cycle then some shortest paths don’t exist
Bellman-Ford algorithm
Bellman-Ford 算法
computes shortest path weights δ(s,v) from source vertex s ∈ V to all vertices v ∈ V
OR reports that a negative weight cycle exists
计算从源顶点s到任意一点的最短路径权重，或者检测出负权环存在，
Exercise compute δ(s,v) even when sorne are -∞
作业 计算所有情况下的 δ
Bellman-Ford(G.W.S)
d[s] <- 0 for each v ∈ V -{s} do d[v] <- ∞ //init for i <-1 to |v|-1 do for each edge(u,v) ∈ E do if d[v] > d[u]+w(u,v) then d[v] <- d[u]+w(u,v) //relaxzation for each edge(u,v) ∈ E do if d[v] > d[u] + w(u,v) then report that a negative-weight cycle exists else d[v] = δ(s,v)time O(V*E)
Q A B C D E 0 ∞ ∞ ∞ ∞ 0-1 ∞ ∞ ∞ 0-1 4 ∞ ∞ 0-1 2 ∞ ∞ i=1 0-1 2 ∞ 1 0-1 2 1 1 0-1 2-2 1 i=2 ... ...It’s guaranteed to converge
优化，在最糟糕情况下，没有什么不同；实际中，如果有一轮循环没有做任何改变，记录，停止循环。
应用，分布式系统，网络上，寻找最短路径
Correctness:
if G=(V,E) has no neg-weight cycles then Bellman-Ford terminates with d[v] = δ(s,v) for all v ∈ V
设有图 G=(V,E)没有负权环，当Bellman-Ford算法结束时， 所有顶点d[v]都会等于最短路径δ值
Proof:
Consider any v ∈ V By monotonicity & Correctness I (d[v] >= δ(s,v)) only need to show that d[v] = δ(s,v) at some time ∵ d值的单调性和Correctness I d[v] >= δ(s,v) ∴ 只需要证明在某一时间点，等式成立 Let p=v_0->v_1->v_2->...->v_k (starts at s ends at v) be a shortest path from s to v with minimum number of edges => p is a simple path s到v的最短路径，且经过最少的边 => p是一个简单路径，顶点不重复的路径（没有0权环） δ(s,v_i) = δ(s,v_(i-1)) + w(v_(i-1),v_i) by optimal substructure d[v_0] = 0 initially = δ(s,v_0) Assume by induction that d[v_j] = δ(s,v_j) after i rounds for j<i (递归）//d[v_i] after i-1 rounds d[v_(i-1)] = δ(s,v_(i-1)) During ith round relax(v_(i-1),v_i) Correctness Lemma => d[v_i] = δ(s,v) After k rounds d[v] = δ(s,v) k <= |v|-1 because p is simpleCorollary: if Bellman-Ford fails to converge after |v|-1 rounds then must be a neg-weight cycle.
linear programming
all pair shortest path 全对最短路径
ScalersTalkID:scalerstalk
本微信公众号作者Scalers，游走在口译世界的IT从业者。微信公众号ScalersTalk，微博@Scalers，网站ScalersTalk.com，口译100小时训练计划群C 456036104
成长会是由Scalers发起的面向成长、实践行动，且凝聚了来自全球各地各行各业从业者的社群。有意入会者请和Scalers直接联系，我和其他会员会和你直接交流关于成长行动等各方面的经验教训。2016年成长会持续招募中，参见做能说会写的持续行动者：ScalersTalk成长会2016年会员计划介绍(2016.3更新)