資訊專欄INFORMATION COLUMN
摘要：對于邊權為正的圖，任意兩個結點之間的最短路，任意一條的結點數不會超過，邊數不會超過。我會說只有三個嗎適用于任何圖，不管有向無向，邊權正負，但是最短路必須存在。
定義
（還記得這些定義嗎？如果對 圖的概念 和 存儲 不了解請點擊鏈接）
路徑
最短路
有向圖中的最短路、無向圖中的最短路
單源最短路、每對結點之間的最短路
性質
對于邊權為正的圖，任意兩個結點之間的最短路，不會經過重復的結點。
對于邊權為正的圖，任意兩個結點之間的最短路，不會經過重復的邊。
對于邊權為正的圖，任意兩個結點之間的最短路，任意一條的結點數不會超過 n ，邊數不會超過 n?1 。
Floyd 算法
是用來求任意兩個結點之間的最短路的。
復雜度比較高，但是常數小，容易實現。（我會說只有三個 for 嗎？）
適用于任何圖，不管有向無向，邊權正負，但是最短路必須存在。（不能有個負環）
實現
我們定義一個數組 fk[y] ，表示只允許經過結點 1 到 k ，結點 x 到結點 y 的最短路長度。
很顯然， fn[y] 就是結點 x 到結點 y 的最短路長度。
我們來考慮怎么求這個數組
f0[y] ：邊權，或者 0 ，或者 +∞ （ f0[x] 什么時候應該是 +∞ ？）
fk[y] = min(fk-1[y] fk-1[k]+fk-1[y])
上面兩行都顯然是對的，然而這個做法空間是 O(N3) 。
但我們發現數組的第一維是沒有用的，于是可以直接改成 fx = min(fx fx+fk) ，
for (int k = 1; k <= n; ++k)
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
f[i][j] = min(f[i][j] f[i][k] + f[k][j]);時間復雜度是 O(N3) ，空間復雜度是 O(N2) 。
應用
"給一個正權無向圖，找一個最小權值和的環。"
首先這一定是一個簡單環。
想一想這個環是怎么構成的。
考慮環上編號最大的結點 u。
fu-1[y] 和 (ux) (uy）共同構成了環。
在 Floyd 的過程中枚舉 u，計算這個和的最小值即可。
O(n3) 。
"已知一個有向圖中任意兩點之間是否有連邊，要求判斷任意兩點是否連通。"
該問題即是求 圖的傳遞閉包 。
我們只需要按照 Floyd 的過程，逐個加入點判斷一下。
只是此時的邊的邊權變為 1/0 ，而取 min 變成了 與 運算。
再進一步用 bitset 優化，復雜度可以到 O(n3w) 。
// std::bitset
for (k = 1; k <= n; k++)
for (i = 1; i <= n; i++)
if (fi) f[i] = f[i] & f[k];
Bellman-Ford 算法
一種基于松弛（relax）操作的最短路算法。
支持負權。
能找到某個結點出發到所有結點的最短路，或者報告某些最短路不存在。
在國內 OI 界，你可能聽說過的“SPFA”，就是 Bellman-Ford 算法的一種實現。（優化）
實現
假設結點為 S 。
先定義 dist(u) 為 S 到 u （當前）的最短路徑長度。
relax(uv) 操作指： dist(v)=min(dist(v)dist(u)+edge_len(uv)) .
relax 是從哪里來的呢？
三角形不等式： dist(v)≤dist(u)+edge_len(uv) 。
證明：反證法，如果不滿足，那么可以用松弛操作來更新 dist(v) 的值。
Bellman-Ford 算法如下：
while (1) for each edge(u v) relax(u v);
當一次循環中沒有松弛操作成功時停止。
每次循環是 O(m) 的，那么最多會循環多少次呢？
答案是 ∞ ！（如果有一個 S 能走到的負環就會這樣）
但是此時某些結點的最短路不存在。
我們考慮最短路存在的時候。
由于一次松弛操作會使最短路的邊數至少 +1 ，而最短路的邊數最多為 n?1 。
所以最多執行 n?1 次松弛操作，即最多循環 n?1 次。
總時間復雜度 O(NM) 。 （對于最短路存在的圖）
relax(u v) {
dist[v] = min(dist[v] dist[u] + edge_len(u v));}
for (i = 1; i <= n; i++) {
dist[i] = edge_len(S i);}
for (i = 1; i < n; i++) {
for each edge(u v) {
relax(u v);
}}
注：這里的 edge_len(uv) 表示邊的權值，如果該邊不存在則為 +∞ ， u=v 則為 0 。
應用
給一張有向圖，問是否存在負權環。
做法很簡單，跑 Bellman-Ford 算法，如果有個點被松弛成功了 n 次，那么就一定存在。
如果 n?1 次之內算法結束了，就一定不存在。
隊列優化：SPFA
即 Shortest Path Faster Algorithm。
很多時候我們并不需要那么多無用的松弛操作。
很顯然，只有上一次被松弛的結點，所連接的邊，才有可能引起下一次的松弛操作。
那么我們用隊列來維護“哪些結點可能會引起松弛操作”，就能只訪問必要的邊了。
q = new queue();
q.push(S);
in_queue[S] = true;
while (!q.empty()) {
u = q.pop();
in_queue[u] = false;
for each edge(u v) {
if (relax(u v) && !in_queue[v]) {
q.push(v);
in_queue[v] = true;
}
}}
雖然在大多數情況下 SPFA 跑得很快，但其最壞情況下的時間復雜度為 O(NM) ，將其卡到這個復雜度也是不難的，所以考試時要謹慎使用（在沒有負權邊時最好使用 Dijkstra 算法，在有負權邊且題目中的圖沒有特殊性質時，若 SPFA 是標算的一部分，題目不應當給出 Bellman-Ford 算法無法通過的數據范圍）。
SPFA 的優化之 SLF
即 Small Label First。
即在新元素加入隊列時，如果隊首元素權值大于新元素權值，那么就把新元素加入隊首，否則依然加入隊尾。
該優化在確實在一些圖上有顯著效果，但是如果有負權邊的話，可以直接卡到指數級。
Dijkstra 算法
Dijkstra 是個人名（荷蘭姓氏）。
IPA:/?dikstrɑ/或/?d?ikstrɑ/。
這種算法只適用于非負權圖，但是時間復雜度非常優秀。
也是用來求單源最短路徑的算法。
實現
主要思想是，將結點分成兩個集合：已確定最短路長度的，未確定的。
一開始第一個集合里只有 S 。
然后重復這些操作：
對那些剛剛被加入第一個集合的結點的所有出邊執行松弛操作。
從第二個集合中，選取一個最短路長度最小的結點，移到第一個集合中。
直到第二個集合為空，算法結束。
時間復雜度：只用分析集合操作， n 次 delete-min ， m 次 decrease-key 。
如果用暴力： O(n2+m)=O(n2) 。
如果用堆 O(mlogn) 。
如果用 priority_queue： O(mlogm) 。
（注：如果使用 priority_queue，無法刪除某一個舊的結點，只能插入一個權值更小的編號相同結點，這樣操作導致堆中元素是 O(m) 的）
如果用線段樹（ZKW 線段樹）： O(mlogn+n)=O(mlogn)
如果用 Fibonacci 堆： O(nlogn+m) （這就是為啥優秀了）。
等等，還沒說正確性呢！
分兩步證明：先證明任何時候第一個集合中的元素的 dist 一定不大于第二個集合中的。
再證明第一個集合中的元素的最短路已經確定。
第一步，一開始時成立（基礎），在每一步中，加入集合的元素一定是最大值，且是另一邊最小值，每次松弛操作又是加上非負數，所以仍然成立。（歸納）（利用非負權值的性質）
第二步，考慮每次加進來的結點，到他的最短路，上一步必然是第一個集合中的元素（否則他不會是第二個集合中的最小值，而且有第一步的性質），又因為第一個集合內的點已經全部松弛過了，所以最短路顯然確定了。
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://m.hztianpu.com/yun/126246.html
摘要：由于是從頂點到的最短路徑，則有。算法流程根據最短路徑的最優子結構性質，提出了以最短路徑長度遞增，逐次生成最短路徑的算法。相關文章王者編程大賽之一王者編程大賽之二蓄水池王者編程大賽之三背包王者編程大賽之四約瑟夫環 首發于 樊浩柏科學院 自如年底就會擁有 50W 間房子，大家知道每間房房子都是需要配置完才能出租給自如客的，整個房租的配置過程是很復雜的，每天都需要大量的物流師傅將家電、家具...
摘要：學習資料迪杰斯特拉計算的是單源最短路徑，而弗洛伊德計算的是多源最短路徑代碼不能設置為，否則兩個相加會溢出導致出現負權創建頂點和邊 學習資料 迪杰斯特拉計算的是單源最...
摘要：推薦資料推薦學習文章代碼不能設置為否則兩個相加會溢出導致出現負權創建頂點和邊創建圖頂點數得到邊的數目調用算法計算最短路徑 推薦資料 推薦學習文章 代碼 public...
摘要：算法系列單源最短路徑算法迪杰斯特拉算法是由荷蘭計算機科學家狄克斯特拉于年提出的，因此又叫狄克斯特拉算法。是從一個頂點到其余各頂點的最短路徑算法，解決的是有向圖中最短路徑問題。 Javascript算法系列 - 單源最短路徑 - Dijkstra算法 迪杰斯特拉算法是由荷蘭計算機科學家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法。是從一個頂點到其余各頂點的最短路徑算法，解決的是有...
摘要：相關操作就是判斷的不等號符號改反，初始值設為負無窮副本的最短路徑即為原圖的最長路徑。方法是同上面一樣構造圖，同時會添加負權重邊，再將所有邊取反，然后求最短路徑最短路徑存在則可行沒有負權重環就是可行的調度。 Algorithms Fourth EditionWritten By Robert Sedgewick & Kevin WayneTranslated By 謝路云Chapter ...
閱讀 3953·2023-04-25 20:09
閱讀 4015·2022-06-28 19:00
閱讀 3504·2022-06-28 19:00
閱讀 3431·2022-06-28 19:00
閱讀 3666·2022-06-28 19:00
閱讀 3223·2022-06-28 19:00
閱讀 3592·2022-06-28 19:00
閱讀 3164·2022-06-28 19:00
