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