10.1 Warshall：transitive closure-19
沃肖爾算法計算二元關(guān)系(或有向圖)的傳遞閉包transitive closure到逊，以矩陣的形式表示管毙。（只有0和1）
如果在圖G中有一條從a到z的路徑，一條邊a, z在圖G的傳遞閉包中
recurrence relation：
k表示stepping stones，即路徑是否經(jīng)過k這個node饵逐。
有兩種情況，1.經(jīng)過上一個墊腳石(k-1)已經(jīng)有i到j(luò)的路徑了绘盟。2.上一個墊腳石有i到k的路徑也有k到j(luò)的路徑。
step:k為x就看第x行和第x列悯仙，先找出x列中為1的數(shù)龄毡，再找出x行中為1的數(shù)，將所有列锡垄、行的組合都標為1（行列數(shù)相同也需要）.
Warshall 總結(jié)
1.最好沦零，最差，平均時間復(fù)雜度都是Θ(n^3)
2.適合dense garphs 稠密圖
3.sparse graphs稀疏圖最好每個節(jié)點輪流做DFS货岭，記錄從每個節(jié)點輪流到達哪些節(jié)點
4.有向圖路操，無向圖都可以用
10.2Floyd’s Algorithm: All-Pairs Shortest-Paths
Floyd總結(jié)
1.Floyd的算法解決了權(quán)值為正 positive weights的圖的全對最短路徑問題all-pairs shortest-path。
2.它適用于有向圖和無向圖千贯。
3.如果節(jié)點i與j之間沒有邊屯仗，我們用∞表達，鄰接矩陣的對角線上的元素總是為0搔谴。
4.“sub-structure” property：全局最優(yōu)解的局部也是最優(yōu)解魁袜，dynamic programming滿足此特質(zhì)
5.求最短距離可以滿足上述特質(zhì)，最長則不可以
10.3 Prim’s algorithm：finding minimum spanning trees
Greedy Algorithms：局部最優(yōu)解就是全局最優(yōu)解的一部分敦第。
Spanning Trees：只使用一部分邊連接全部的節(jié)點峰弹，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為標準構(gòu)造優(yōu)先隊列
prim 總結(jié)
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| ). 時間復(fù)雜度為 (|V|?1+|E| )Ο(log |V| ),因為|V|?1<|E|,所以時間復(fù)雜度為 Ο(|E| log |V|)
10.4Dijkstra’s algorithm：single-source shortest path tree
與Floyd’s algorithm找所有節(jié)點的最短路徑不同垮卓，Dijkstra只找一條最短路徑
雖然已經(jīng)經(jīng)過了b，但在從c走的path上不需要加上a到b的weight师幕，如，c到d的weight是10诬滩，而不是14
Dijkstra 總結(jié)
1.時間復(fù)雜度為 Ο(|E| log |V|)
2.與prim不同霹粥，Dijkstra在計算下一次最短路徑時需要加上上一次的weight
3.最后得到的是shortest-path tree，而不是最短path疼鸟，path可以不用經(jīng)過每一個節(jié)點后控。
4.只應(yīng)用于正權(quán)值的圖，負權(quán)值可以使用Bellman-Ford algorithm
