圖論最短路徑問題
最最原始的問題——兩點(diǎn)間的最短路
這類背景一般是類似：已知各城市之間距離，請給出從城市A到城市B的最短行車方案 or 各城市距離一致凿滤，給出需要最少中轉(zhuǎn)方案。
深度優(yōu)先搜索（dfs)
- DFS算法關(guān)鍵思想僅在于解決當(dāng)下該如何做济竹。至于“下一步如何做”則與“當(dāng)下該如何做”是一樣的惋啃，把參數(shù)改為進(jìn)入下一步的值再調(diào)用一下dfs()即可。
- 而在寫dfs函數(shù)的時(shí)候就只要解決當(dāng)在第step的時(shí)候你該怎么辦毅该，通常就是把每一種可能都去嘗試一遍博秫。當(dāng)前這一步解決后便進(jìn)入下一步dfs(step+1)，剩下的事情就不用管它了眶掌。
基本模型：
void dfs(int step)
{
判斷邊界
嘗試每一種可能 for(int i = 1; i <= n; i++)
{
繼續(xù)下一步 dfs(step+1)
}
}
廣度優(yōu)先搜索
- 對于所有邊權(quán)相同的情況挡育，用廣度優(yōu)先搜索會更快更方便。
- 比如上面提到的最少中轉(zhuǎn)方案問題朴爬，問從城市1到城市4需要經(jīng)過的最少中轉(zhuǎn)城市個(gè)數(shù)即寒。
int bfs()
{
queue<pair<int,int>> que; //pair記錄城市編號和dis，也可以用結(jié)構(gòu)體
que.push({1,0}); //把起始點(diǎn)加入隊(duì)列
book[1] = 1; //標(biāo)記為已在路徑中
while(!que.empty())
{
int cur = que.front();
que.pop();
for(int i = 1; i <= n; i++)
{
if(e[cur][i] != MAX && book[i] == 0) //若從cur到i可達(dá)且i不在隊(duì)列中召噩，i入隊(duì)
{
que.push({i, cur.second+1});
book[i] = 1;
if(i == n) return cur.second; //如果已擴(kuò)展出目標(biāo)結(jié)點(diǎn)了蒿叠，返回中轉(zhuǎn)城市數(shù)答案
}
}
}
}
Floyd算法
- 膨脹——任意兩點(diǎn)間的最短路
- 已經(jīng)知道了求解固定兩點(diǎn)間的最短路，那要怎么求任意兩點(diǎn)間的最短路呢蚣常？
-
顯然，可以進(jìn)行n^2 次的dfs或bfs輕松搞定（被打）痊银。
- 觀察會發(fā)現(xiàn)抵蚊，如果要讓兩點(diǎn) i , j 間的路程變短，只能通過第三個(gè)點(diǎn) k 的中轉(zhuǎn)溯革。
- 比如上面第一張圖贞绳，從 1->5 距離為10，但 1->2->5 距離變成9了致稀。
- 事實(shí)上冈闭，每個(gè)頂點(diǎn)都有可能使另外兩個(gè)頂點(diǎn)間的路程變短。這種通過中轉(zhuǎn)變短的操作叫做松弛抖单。
- 當(dāng)任意兩點(diǎn)間不允許經(jīng)過第三個(gè)點(diǎn)時(shí)萎攒，這些城市之間的最短路程就是初始路程：
- 假如現(xiàn)在允許經(jīng)過1號頂點(diǎn)的中轉(zhuǎn)，求任意兩點(diǎn)間的最短路矛绘，這時(shí)候就可以遍歷每一對頂點(diǎn)耍休，試試看通過1號能不能縮短他們的距離。
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
{
if(e[i][j] > e[i][1]+e[1][j]) e[i][j] = e[i][1]+e[1][j];
}
- 擴(kuò)展一下货矮，先允許1號頂點(diǎn)作為中轉(zhuǎn)給所有兩兩松弛一波羊精，再允許2號、3號...n號都做一遍囚玫，就能得到最終任意兩點(diǎn)間的最短路了喧锦。
- 這就是Floyd算法读规，雖然時(shí)間復(fù)雜度是令人發(fā)怵的O(n^3)，但核心代碼只有五行燃少，實(shí)現(xiàn)起來非常容易束亏。
for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(e[i][j] > e[i][k]+e[k][j])
e[i][j] = e[i][k]+e[k][j];
單源最短路 Dijkstra
- 指定源點(diǎn)，求它到其余各個(gè)結(jié)點(diǎn)的最短路供汛。
- 比如給出這張圖枪汪，假設(shè)把1號結(jié)點(diǎn)作為源點(diǎn)。
- 還是用數(shù)組dis來存1號到其余各點(diǎn)的初始路程：
- 既然是求最短路徑怔昨，那先選一個(gè)離1號最近的結(jié)點(diǎn)雀久，也就是2號結(jié)點(diǎn)。這時(shí)候趁舀，dis[2]=1 就固定了赖捌，它就是1到2的最短路徑。這是為啥矮烹？因?yàn)槟壳半x1號最近的是2號越庇，且這個(gè)圖的所有邊都是正數(shù)，那就不可能能通過第三個(gè)結(jié)點(diǎn)中轉(zhuǎn)使得距離進(jìn)一步縮短了奉狈。因?yàn)閺?號出發(fā)已經(jīng)找不到哪條路比直接到達(dá)2號更短了卤唉。
- 選好了2號結(jié)點(diǎn)，現(xiàn)在看看2號的出邊仁期，有2->3和2->4桑驱。先討論通過2->3這條邊能否讓1號到3號的路程變短，也即比較dis[3]和dis[2]+e[2][3]的大小跛蛋。發(fā)現(xiàn)是可以的熬的，于是dis[3]從12變?yōu)樾碌母搪?0。同理赊级，通過2->4也條邊也更新下dis[4]押框。
- 松弛完畢后dis數(shù)組變?yōu)椋?/li>
- 接下來，繼續(xù)在剩下的 3 4 5 6 結(jié)點(diǎn)中選一個(gè)離1號最近的結(jié)點(diǎn)理逊。發(fā)現(xiàn)當(dāng)前是4號離1號最近橡伞，于是dis[4]確定了下來，然后繼續(xù)對4的所有出邊看看能不能做松弛挡鞍。
- 這樣一直做下去直到已經(jīng)沒有“剩下的”結(jié)點(diǎn)骑歹，算法結(jié)束。
- 這就是Dijkstra算法墨微，整個(gè)算法的基本步驟是：
- 所有結(jié)點(diǎn)分為兩部分：已確定最短路的結(jié)點(diǎn)集合P道媚、未知最短路的結(jié)點(diǎn)集合Q。最開始，P中只有源點(diǎn)這一個(gè)結(jié)點(diǎn)最域。（可用一個(gè)book數(shù)組來維護(hù)是否在P中）
- 在Q中選取一個(gè)離源點(diǎn)最近的結(jié)點(diǎn)u（dis[u]最星捶帧）加入集合P。然后考察u的所有出邊镀脂，做松弛操作牺蹄。
- 重復(fù)第二步，直到集合Q為空薄翅。最終dis數(shù)組的值就是源點(diǎn)到所有頂點(diǎn)的最短路沙兰。
for(int i = 1; i <= n; i++) dis[i] = e[1][i]; //初始化dis為源點(diǎn)到各點(diǎn)的距離
for(int i = 1; i <= n; i++) book[i] = 0;
book[1] = 1; //初始時(shí)P集合中只有源點(diǎn)
for(int i = 1; i <= n-1; i++) //做n-1遍就能把Q遍歷空
{
int min = INF;
int u;
for(int j = 1; j <= n; j++) //尋找Q中最近的結(jié)點(diǎn)
{
if(book[j] == 0 && dis[j] < min)
{
min = dis[j];
u = j;
}
}
book[u] = 1; //加入到P集合
for(int v = 1; v <= n; v++) //對u的所有出邊進(jìn)行松弛
{
if(e[u][v] < INF)
{
if(dis[v] > dis[u] + e[u][v])
dis[v] = dis[u] + e[u][v];
}
}
}
- Dijkstra是一種基于貪心策略的算法。每次新擴(kuò)展一個(gè)路徑最短的點(diǎn)翘魄，更新與它相鄰的所有點(diǎn)鼎天。當(dāng)所有邊權(quán)為正時(shí)，由于不會存在一個(gè)路程更短的沒擴(kuò)展過的點(diǎn)暑竟，所以這個(gè)點(diǎn)的路程就確定下來了斋射，這保證了算法的正確性。
- 但也正因?yàn)檫@樣但荤，這個(gè)算法不能處理負(fù)權(quán)邊罗岖，因?yàn)閿U(kuò)展到負(fù)權(quán)邊的時(shí)候會產(chǎn)生更短的路徑，有可能破壞了已經(jīng)更新的點(diǎn)路程不會改變的性質(zhì)腹躁。
Bellman-Ford算法
- 于是桑包，Bellman-Ford算法華麗麗的出場啦。它不僅可以處理負(fù)權(quán)邊纺非，而且算法思想優(yōu)美捡多，且核心代碼只有短短四行。
（用三個(gè)數(shù)組存邊铐炫，第i條邊表示u[i]->v[i]，權(quán)值為w[i]）
for(int k = 1; k <= n-1; k++)
for(int i = 1; i <= m; i++)
if(dis[v[i]] > dis[u[i]] + w[i])
dis[v[i]] = dis[u[i]] + w[i];
- 后兩行代碼的意思是蒜焊，看看能否通過u[i]->v[i]這條邊縮短dis[v[i]]倒信。加上第二行的for，也就是把所有的m條邊一個(gè)個(gè)拎出來泳梆，看看能不能縮短dis[v[i]]（松弛）鳖悠。
- 那把每一條邊松弛一遍后有什么效果呢？
- 比如求這個(gè)例子：
- 同樣用dis數(shù)組來存儲1號到各結(jié)點(diǎn)的距離优妙。一開始時(shí)只有dis[1]=0乘综，其他初始化為INF。
- 先來處理第一條邊 2->3 套硼，然鵝dis[3]是INF卡辰，dis[2]+2也是INF，松弛失敗。
第二條邊 1->2 九妈，dis[2]是INF反砌，dis[1]-3是-3，松弛成功萌朱，dis[2]更新為-3宴树。 - 就這樣對所有邊松弛一遍后的結(jié)果如下：
- 這時(shí)候dis[2]和dis[5]的值變小了，如果再做一輪松弛操作的話晶疼，之前不成功的松弛這時(shí)候也能也就可以起作用了酒贬。
- 換句話說，第一輪松弛后得到的是從1號出發(fā)“只能經(jīng)過1條邊”到達(dá)其余各點(diǎn)的最短路翠霍，第二輪松弛后得到的是“只能經(jīng)過2條邊”到達(dá)其余各點(diǎn)的最短路锭吨，如果進(jìn)行第k輪松弛得到的就是“只能經(jīng)過k條邊”到達(dá)其余各點(diǎn)的最短路。
- 那么到底需要進(jìn)行多少輪呢壶运？答案是n-1輪耐齐。因?yàn)樵谝粋€(gè)含有n個(gè)頂點(diǎn)的圖中，任意兩點(diǎn)間的最短路最多包含n-1條邊蒋情。也就解釋了代碼的第一行埠况，是在進(jìn)行n-1輪松弛。
for(int i = 1; i <= n; i++) dis[i] = INF;
dis[1] = 0; //初始化dis數(shù)組棵癣，只有1號的距離為0
for(int k = 1; k <= n-1; k++) //進(jìn)行n-1輪松弛
for(int i = 1; i <= m; i++) //枚舉每一條邊
if(dis[v[i]] > dis[u[i]] + w[i]) //嘗試進(jìn)行松弛
dis[v[i]] = dis[u[i]] + w[i];
- 此外辕翰，Bellman-Ford算法還可以檢測一個(gè)圖是否含有負(fù)權(quán)回路。如果在進(jìn)行了n-1次松弛之后狈谊，仍然存在某個(gè)dis[v[i]] > dis[u[i]] + w[i]的情況喜命，還可以繼續(xù)成功松弛，那么必然存在回路了（因?yàn)檎碇v最短路徑包含的邊最多只會有n-1條）河劝。
- 判斷負(fù)權(quán)回路也即在上面那段代碼之后加上一行：
for(int i = 1; i <= m; i++)
if(dis[v[i]] > dis[u[i]] + w[i]) flag = 1;
- Bellman-Ford算法的時(shí)間復(fù)雜度是O(nm)壁榕，貌似比Dijkstra還高。
- 事實(shí)上還可以進(jìn)行優(yōu)化赎瞎，比如可以加一個(gè)bool變量check用來標(biāo)記數(shù)組dis在本輪松弛中是否發(fā)生了變化牌里，如果沒有，就可以提前跳出循環(huán)务甥。因?yàn)槭恰白疃唷边_(dá)到n-1輪筛峭，實(shí)際情況下經(jīng)常是早就已經(jīng)達(dá)到最短僧界，沒法繼續(xù)成功松弛了藤乙。
for(int k = 1; k <= n-1; k++) //進(jìn)行n-1輪松弛
{
bool check = 0;
for(int i = 1; i <= m; i++) //枚舉每一條邊
if(dis[v[i]] > dis[u[i]] + w[i]) //嘗試進(jìn)行松弛
{
dis[v[i]] = dis[u[i]] + w[i];
check = 1;
}
if(check == 0) break;
}
SPFA算法（隊(duì)列優(yōu)化的Bellman-Ford）
- 另外一種優(yōu)化是：每次僅對最短路估計(jì)值發(fā)生了變化的結(jié)點(diǎn)的所有出邊進(jìn)行松弛操作外盯。因?yàn)樵谏厦娴乃惴ㄖ校繉?shí)施一次松弛操作后挺尿，就會有一些頂點(diǎn)已經(jīng)求得最短路之后便不會再改變了（由估計(jì)值變?yōu)榇_定值）奏黑，既然都已經(jīng)不受后續(xù)松弛操作的影響了卻還是每次都要判斷是否需要松弛炊邦，就浪費(fèi)了時(shí)間。
- 可以用隊(duì)列來維護(hù)dis發(fā)生了變化的那些結(jié)點(diǎn)攀涵。具體操作是：
- 初始時(shí)將源點(diǎn)加入隊(duì)列铣耘。
- 每次選取隊(duì)首結(jié)點(diǎn)u，對u的所有出邊進(jìn)行松弛以故。假設(shè)有一條邊u->v松弛成功了蜗细，那就把v加入隊(duì)列。然而怒详，同一個(gè)結(jié)點(diǎn)同時(shí)在隊(duì)列中出現(xiàn)多次是毫無意義的（可以用一個(gè)bool數(shù)組來判哪些結(jié)點(diǎn)在隊(duì)列中）炉媒。所以剛提到的操作其實(shí)是，如果v不在當(dāng)前隊(duì)列中昆烁，才把它加入隊(duì)列吊骤。
- 對u的所有出邊松弛完畢后，u出隊(duì)静尼。接下來不斷的取出新的隊(duì)首做第2步操作白粉，直到隊(duì)列為空。
- 一個(gè)例子：
- 用數(shù)組dis來存放1號結(jié)點(diǎn)到各點(diǎn)的最短路鼠渺。初始時(shí)dis[1]為0鸭巴。接下來將1號結(jié)點(diǎn)入隊(duì)。
- 現(xiàn)在看1號的所有出邊拦盹，對于1->2鹃祖，比較dis[2]和dis[1]+e[1][2]的大小，發(fā)現(xiàn)松弛成功普舆，dis[2]從INF變?yōu)?恬口。并且2不在隊(duì)列中，所以2號結(jié)點(diǎn)入隊(duì)沼侣。同理祖能，5號結(jié)點(diǎn)也松弛成功，入隊(duì)蛾洛。
- 1號結(jié)點(diǎn)處理完畢芯杀，此時(shí)將1號出隊(duì)，接著對隊(duì)首也就是2號結(jié)點(diǎn)進(jìn)行同樣的處理雅潭。在處理2->5這條邊的時(shí)候，雖然松弛成功却特，dis[5]從10更新為9了扶供，但5號頂點(diǎn)已經(jīng)在隊(duì)列中，所以5號不能再次入隊(duì)裂明。
- 處理完2號之后就長這樣：
- 接著一直持續(xù)下去椿浓，直到隊(duì)列為空，算法結(jié)束。
for(int i = 1; i <= n; i++) book[i] = 0; //初始時(shí)都不在隊(duì)列中
queue<int> que;
que.push(1); //將結(jié)點(diǎn)1加入隊(duì)列
book[1] = 1; //并打標(biāo)記
while(!que.empty())
{
int cur = que.empty(); //取出隊(duì)首
for(int i = 1; i <= n; i++)
{
if(e[cur][i] != INF && dis[i] > dis[cur]+e[cur][i]) //若cur到i有邊且能夠松弛
{
dis[i] = dis[cur]+e[cur][i]; //更新dis[i]
if(book[i] == 0) //若i不在隊(duì)列中則加入隊(duì)列
{
que.push(i);
book[i] = 1;
}
}
}
que.pop(); //隊(duì)首出隊(duì)
book[cur] = 0;
}
- 這其實(shí)就是SPFA算法（隊(duì)列優(yōu)化的Bellman-Ford）扳碍，它的關(guān)鍵思想就在于：只有那些在前一遍松弛中改變了最短路估計(jì)值的結(jié)點(diǎn)提岔，才可能引起它們鄰接點(diǎn)最短路估計(jì)值發(fā)生改變。
- 它也能夠判斷負(fù)權(quán)回路：如果某個(gè)點(diǎn)進(jìn)入隊(duì)列的次數(shù)超過n次笋敞，則存在負(fù)環(huán)碱蒙。
最短路徑算法的對比
