Algorithms第4章及少量习题
这一章的题目叫做Paths in graphs。讲的是图之间的最短路问题。主要讲了BFS,Dijkstra[普通实现，Binary heap实现，d-ary heap实现，fibonacci heap实现]和Bell-Ford算法。这本书上引出这些算法的例子我觉得用的很好。
首先是通过DFS引出BFS，给出一个简单图，如果你进行一次BFS的话，那么得到的那些pre和post值是不能反应源点到其他点的距离的。下面的图分别是DFS-tree和S 到各点的距离图
由上面的图可知，DFS是不能很好的得到S到其他点之间的最短距离的。很明显在DFS-tree中S和C的距离很远，但实际上他们之间的距离却很短。这样就引出了BFS，如下面代码所示
Input: Graph G = (V, E), directed or undirected vertex s in V
Output: For all vertices u reachable from s, dist(u) is set to
the distance from s to u.
for all u in V
dist(u) = infdist(s) = 0
Q = [s] (queue containing just s)
while Q is not empty:
u = eject(Q)
for all edges (u,v) in E:
if dist(v) = inf:
inject(Q, v)
dist(v) = dist(u) + 1
实际上就是每一次把和所处理的点相邻的所有点都放进队列里面，利用队列先进先出的性质，可以做到依次得到所有点离源点的距离。
不过BFS在实际应用中有一个约束，也就是说需要所有的边长都是1,但这个在实际应用中是很难做到的。那么我们可以考虑在相邻的两个点之间插入一系列的辅助点，也就是说变长为L的话，那么我们就插入L-1个辅助点，这样的话，所有的边都变成了变长为1，就可以用BFS来处理了，但是这里有一个问题，如果有两个点之间的距离非常长的话，那么我们就会在插入辅助点这一点上做很多“无用功”，而且我们不关心某个点到这些辅助点之间的距离，那么我们就可以想到这样，如果有下面一种类似“alarm clock”的算法的话，我们还是在每两个点之间插入相应的辅助点，但是只有当计算机访问到实际点的时候，clock才会响，这样哦我们就知道了，这个点离源点有多远了[clock响的时间就是需要的距离]那么我们就可以在图上进行BFS了
1.把源点s的alarm clock设置为0,也就是说在第0时刻，源点所在的clock会响
2.执行下面的操作，直到不需要再设置alarm clock为止
//我们说如果一个clokc在T时刻响了，那么源点到这个点的距离就是T，对所有的顶点u
源点s到u的距离是T
对所有u的邻接点v
如果v还没有被设置alarm clock，那么就把v处的alarm clock设置为T+len[u,v]
如果v处的alarm clock被设置得被T+len[u,v]晚，那么就把它更新为T+len[u,v]
这样的话我们就得到了这个Dijkstra算法的大致实现了，这里我们只需要用到一个priority queue来实现如下的一系列操作就可以完成Dijkstra算法了
Insert： 把一个新的元素加到集合里面
Decrease-key： 更新集合里面某个元素的值[这里是减小]
Delete-min： 删掉并返回集合中的最小值
Make-queue：利用一系列的给定值建立一个priority queue。
前两个操作可以让我们实现设置alarm clock的操作，第三个则会告诉我们接下来哪个alarm clock会响，把这些放在一起就得到了Dijkstra算法了，伪代码如下：
Input: Graph G = (V, E), directed or undirected
positive edge lengths e in E vertex s in V
Output: For all vertices u reachable from s, dist(u)
is set to the distance from s to u
for all u in V
dist(u) = inf
pre(u) = nildist(s) = 0H = makequeue(V) (using dist-values as keys)
while H is not empty:
u = deletemin(H)
for all edges (u,v) in E
if dist(v) > dist(u) + l(u,v)
dist(v) = dist(u) + l(u,v)
pre(v) = u
decreasekey(H, v)
Dijkstra算法要求所有的边都是正的，这是因为要保证已经deletemin的点的最短距离不会改变，如果有负边的话，那么就会变成后面的Bellman-Ford算法，后面会说。其中的priority queue一般有几种实现。一个是直接用数组存，这样的话deletemin的时间是O(V)，insert/decreasekey的时间是O(1)，所有总时间为Vdeletemin+(V+E)insert[可以由上面的伪代码得到]。总时间是V^2.同样Binary heap实现的话可以得到的时间复杂度为O((V+E)logV)，Binary heap的deletemin和insert/decreasekey都是logV的。还有d-ary heap的话，时间复杂度为O((Vd+E)logV/logd).Fibonacci heap的时间复杂度为O(VlogV+E)但是Fibonacci heap实现太麻烦，所以基本是用的数组或者Binary heap。还有到底数组和Binary heap的实现，谁更快呢？就要看图是否稀疏了，稀疏的话，Binary heap的会好些，也就是E<V^2/logV的时候，E超过这个之后，数组实现的反而会好一些。
接下来就是如果图中的边有负的话，那么用Dijkstra算法会怎样呢？会失败。如下图
这样的话，A点的距离确定之后是不会再次改变的，但是实际上是需要改变的。这样就引出了Bellman-Ford算法了，也就是说每个点的距离算出来之后，但是不把它设为不可更改的，而是可以在下次更改，这样的话，一条路径最多包含V个点，那么我们只需要进行V-1次边的松弛操作就行了，松弛操作就是说对于所有的边
Input: Directed graph G = (V, E);
edge lengths e in E with no negative cycles
vertex s in V
Output: For all vertices u reachable from s, dist(u) is set
to the distance from s to u.
for all u in V
dist(u) = inf
pre(u) = nildist(s) = 0
repeat V-1 times:
for all e in E:
update(e) //松弛操作
这样的话，对于图中没有负环的情况下，我们已经能够很好的处理了，如果有负环呢？那么我们可以在Bellman-Ford的repeat之后再对所有边进行一次松弛操作，如果有边的dist变了，那么就一定有负环，否则就没有负环。
接下来是部分习题和解答：
4.3 给一个无向图，需要给一个V^3的算法，判断是否存在一个长为4的simple cycle[a cycle doesn’t intersect itself].
可以跑BFS，如果在将要访问一个点的时候，这个点已经被访问过了，而且两次的长度和为4的话，就可以了。这样需要枚举所有点，把枚举的点当成环中的一个点，BFS的时间复杂度为V+E，枚举是V，所以最多是V^3。
4.6 给一个无向图，需要用线性时间计算出给定两点u和v之间有多少条不同的最短路。
我们只需要记录一个数组p[i].存的是u到i有多少条不同的最短路径就行了。接下来就是用BFS跑一次就可以了。更新的时候，if(dist(i)+len[i,j]<dist[j])的话dist[j]=dist[i]+len[i,j],p[j] = p[i].如果dist[i]+len[i,j] == dist[j]的话，那么p[j]=p[j]+[[i].
4.8对于有负边的图，可以不可以通过把每条边都加一个很大的数变成正的之后，然后跑Dijkstra算法。
不可以，因为这样会改变原图中的最短路径。比如A->B长为-2.A->C长为3,B->C长为4.在为加之前A到C的最短路径为A->B->C，但是每条边都加上2或一个更大的值之后，就变成了A->C
4.9对于只有一条负边，且这条负边是从源点出去的图，能不能用Dijkstra算法。
能，因为符合Dijkstra的条件，某个点的距离一旦确定之后，就不会改变，已经确定的点的距离比为确定的点的距离要小。
4.15给定一个无向图，所有的边都是正的，问能不能在O((V+E)logV)的时间内，确定源点到其他任意点的最短路径是否唯一
这个问题其实和上面的4.6是同一个问题，这里O((V+E)logV)其实就是Binary heap实现的Dijkstra算法的时间复杂度。在图上跑一次Dijkstra算法就可以了。上面的p数组记录的是源点到这个点的最短路径是不是唯一就行了
