10.1 Warshall：transitive closure-19
沃肖尔算法计算二元关系(或有向图)的传递闭包transitive closure，以矩阵的形式表示。（只有0和1）
如果在图G中有一条从a到z的路径，一条边a, z在图G的传递闭包中
recurrence relation：
k表示stepping stones，即路径是否经过k这个node。
有两种情况，1.经过上一个垫脚石(k-1)已经有i到j的路径了。2.上一个垫脚石有i到k的路径也有k到j的路径。
step:k为x就看第x行和第x列，先找出x列中为1的数，再找出x行中为1的数，将所有列、行的组合都标为1（行列数相同也需要）.
Warshall 总结
1.最好，最差，平均时间复杂度都是Θ(n^3)
2.适合dense garphs 稠密图
3.sparse graphs稀疏图最好每个节点轮流做DFS，记录从每个节点轮流到达哪些节点
4.有向图，无向图都可以用
10.2Floyd’s Algorithm: All-Pairs Shortest-Paths
Floyd总结
1.Floyd的算法解决了权值为正 positive weights的图的全对最短路径问题all-pairs shortest-path。
2.它适用于有向图和无向图。
3.如果节点i与j之间没有边，我们用∞表达，邻接矩阵的对角线上的元素总是为0。
4.“sub-structure” property：全局最优解的局部也是最优解，dynamic programming满足此特质
5.求最短距离可以满足上述特质，最长则不可以
10.3 Prim’s algorithm：finding minimum spanning trees
Greedy Algorithms：局部最优解就是全局最优解的一部分。
Spanning Trees：只使用一部分边连接全部的节点，tree是 a connected graph with no cycle树没有cycle但每个点都能连接
organise the nodes that are not yet included in the spanning tree T as a priority queue, organised in a min-heap by edge cost. 以cost为标准构造优先队列
prim 总结
1.是greedy algorithm，采用迭代方法
2.使用adjacency lists和a min-heap for the priority queue，我们做了|V|− 1 heap deletions (每次花费Ο log|V|) 和|E| 次updates of priorities (每次花费Ο log|V| ). 时间复杂度为 (|V|−1+|E| )Ο(log |V| ),因为|V|−1<|E|,所以时间复杂度为 Ο(|E| log |V|)
10.4Dijkstra’s algorithm：single-source shortest path tree
与Floyd’s algorithm找所有节点的最短路径不同，Dijkstra只找一条最短路径
虽然已经经过了b，但在从c走的path上不需要加上a到b的weight，如，c到d的weight是10，而不是14
Dijkstra 总结
1.时间复杂度为 Ο(|E| log |V|)
2.与prim不同，Dijkstra在计算下一次最短路径时需要加上上一次的weight
3.最后得到的是shortest-path tree，而不是最短path，path可以不用经过每一个节点。
4.只应用于正权值的图，负权值可以使用Bellman-Ford algorithm
