求圖的最短路徑（詳談Floyd和Dijkstra）
（注：在這一部分起點、源點意思相近沮尿；點的距離丛塌、邊的長度、權(quán)值意思相近）
（再注：這里面包含一個隱含知識點畜疾，遇到有關圖的問題時部分同學會感到無從下手赴邻，無法把握數(shù)據(jù)規(guī)模，其實一個包含n個點的圖啡捶，最多包含n*（n-1）條通路姥敛，知道了這一點，也就對數(shù)據(jù)規(guī)模有所把握了届慈。筆者看多許多教參都沒有提到這一點徒溪，所以想在最開始講最短路前提一下這一點。這一點也非常好證明金顿，每個點可能有若干的入度和出度臊泌，但是每條邊只有一個出度一個入度這樣兩個維度，所以邊的數(shù)量的規(guī)模最大就是n的平方揍拆，想要加深理解的話還可以化成一張n行n列的二維表格（一個包含n個點的圖）渠概，行坐標表示邊的入度（出發(fā)點），列坐標表示出度（目標點）嫂拴，[i][j]所在的格子就是連接i和j的邊播揪，邊的數(shù)量最多不多于格子的數(shù)量即n*n，n的平方）
（1）最短路徑的概念
什么是最短路徑問題筒狠，這個問題有著大量的生產(chǎn)實際背景猪狈。事實上大至海陸空各種運輸小至一個人每天上班，都會遇到這一問題辩恼。甚至有些問題從表面上看與最短路問題沒有什么關系雇庙，卻也可以歸結(jié)為最短路問題谓形。
設有一個鐵路系統(tǒng)連接著若干城市，x0是系統(tǒng)中的一個固定城市（比如首都或者省會城市）疆前，在該系統(tǒng)中試求x0到其他各城市的最短路線寒跳，這個問題就稱為最短路問題。
我們用一個帶權(quán)圖表示這個鐵路系統(tǒng)竹椒，權(quán)值表示城市之間的鐵路里程童太，于是最短路問題就歸結(jié)為在帶權(quán)圖中找出頂點x0到其他頂點y且具有最小權(quán)的路徑。
更一般的最短路問題的提法是：設（D胸完，w）是有正值加權(quán)的簡單有向圖书释，x0是D中的一個固定頂點，尋找從x0到其他頂點y且具有最小權(quán)的有向圖舶吗。
（2）求圖的最短路徑算法
求圖中兩點的最短路徑問題征冷，可歸結(jié)為①源點（起點）固定，終點不確定的兩點間最短路徑②求圖中任意兩點間的最短路徑誓琼。
對于第一類問題，我們經(jīng)常采用Dijkstra算法肴捉；對于第二類問題腹侣，我們可以采用Floyd算法。
理論上來說先有Dijkstra算法（1959年）后有Floyd算法（1962年）齿穗，上面的實際問題也是從第一類問題向第二類問題推廣傲隶，但是我還是準備先講Floyd算法再講Dijkstra算法。因為從“特殊”到“一般”（類似于數(shù)學中的“數(shù)學歸納法”）需要強大的歸納能力窃页，而從學習者的角度出發(fā)從“一般”到“特殊”則要簡單許多跺株。
我們先來比較一下兩種算法：
Floyd算法是多源最短路算法，時間復雜度為（n的三次方）脖卖，通常用在點比較少乒省，源點（起點）不固定的問題中，能夠解決權(quán)值為負的情況畦木。
Dijkstra算法是單源最短路算法袖扛，時間復雜度通常為（n的平方），不能夠解決權(quán)值為負的情況十籍。
Floyd算法
Floyd算法比較簡單蛆封，就是暴力枚舉了所有的可能，將所有可能找遍就知道了兩點之間的最短路
參數(shù)解釋
Chara數(shù)組 ：儲存兩點間的距離勾栗，Chara[i][j]的值就是點i到點j的距離惨篱。
n：總共有n個點。
p[i][j]:代表對應頂點的最小路徑的前驅(qū)矩陣
MAX：定義最大值围俘，路不通的情況距離就是MAX
算法思想
很容易理解砸讳，我們從一個點i到另一個點j,無非就兩種走法
直接從i到j
通過中間點k中轉(zhuǎn)机断，i->k->j
所以我們就遍歷所有情況，如果通過某個中轉(zhuǎn)點距離小于直接到達的距離绣夺，就更新這兩點間的距離吏奸。
if(Chara[i][j] > Chara[i][k] + Chara[k][j])
Chara[i][j] = Chara[i][k] + Chara[k][j];
代碼
#define MAX 65535
int Chara[N][N],p[N][N];
int n,m;
void Floyd()
{
? for(int i=0;i<n;i++)
? ? {
? ? ? for(int j=0;j<n;j++)
? ? ? {
? ? ? ? ? p[i][j]=j;//初始化
? ? ? ? }
? ? }
? ? for(int k=0;k<n;k++)//中介點
? ? {
? ? ? ? for(int i=0;i<n;i++)//起始點源點
? ? ? ? {
? ? ? ? ? ? for(int j=0;j<n;j++)//目標點終點
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if(Chara[i][k] == MAX || Chara[k][j] == MAX) continue;//暫時不通
? ? ? ? ? ? ? ? if(Chara[i][j] > Chara[i][k] + Chara[k][j])
? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? //如果經(jīng)過下標k頂點路徑比原兩點間路徑更短
? ? ? ? ? ? ? ? ? ? //將當前兩點權(quán)值設為更小的那一個
? ? ? ? ? ? ? ? ? ? ? Chara[i][j] = Chara[i][k] + Chara[k][j];
? ? ? ? ? ? ? ? ? ? ? p[i][j]=p[i][k];//路徑設置經(jīng)過下標k的頂點
? ? ? ? ? ? }
? ? ? ? }
? ? }
}
注：
這里的三重循環(huán)相當于先確立（假定）一個中介點，然后窮舉源點和終點
每個Chara[i][j]里存放的值是i到j的距離陶耍，注意哦i和j是可以不直接相連的甚至可以有多種通路奋蔚。
Floyd最終窮舉了整張圖，得到一個n*n的二維表格Chara烈钞，整張表格你可以視為是以行坐標i為源點泊碑，列坐標j為終點，每個Chara[i][j]的值就是從i到j的最短路的距離毯欣。
Dijkstra算法
Dijkstra算法算是貪心思想實現(xiàn)的馒过，首先把起點到所有點的距離存下來找個最短的，然后松弛一次再找出最短的酗钞，所謂的松弛操作就是腹忽，遍歷一遍看通過剛剛找到的距離最短的點作為中轉(zhuǎn)站會不會更近，如果更近了就更新距離砚作，這樣把所有的點找遍之后就存下了起點到其他所有點的最短距離窘奏，下面仔細講。
算法思想
在具體講Dijkstra之前葫录，我們先來做個對比着裹，F(xiàn)loyd算法是窮舉了整張圖，得到一張二維表米同，n個點一共n行骇扇，第i行的一系列值就表示表示以i為起點到其他各點的最短路徑。單源最短路Dijkstra是源點確定時該源點到其他各點的最短路徑面粮。聰明的同學一定發(fā)現(xiàn)了少孝，哎，這么說來但金，假如Dijkstra中的源點為i0韭山，那么我在Floyd的二維表找到第i0行不就解決問題了嗎？恭喜你冷溃，答對了钱磅，就是這樣。事實上Floyd中的第i0行就是我們所要求的結(jié)果似枕。但是在最開始的兩種算法的比較中也提到了Floyd的時間復雜度是n的三次方盖淡，他把每一行全都求出來了，而許多實際問題中我們只需要特定的那一行凿歼，并且在數(shù)據(jù)較大的時候褪迟，在算法競賽中非常容易超時冗恨，此時就需要用到Dijkstra算法了。（由此可見Dijkstra其實就是Floyd的一種特殊情況味赃，所以筆者想采用從一般到特殊的敘述方式）
回想一下剛剛的Floyd是怎么做的掀抹，三重循環(huán)首先選出中介值k然后窮舉起始點i和目標點j。Dijkstra里目標點i確定只需要循環(huán)k和j即可心俗，二重循環(huán)時間復雜度自然是n的平方了傲武。
那么問題來了，直接在Floyd的三重循環(huán)里面刪除其中的源點循環(huán)就可以了嗎城榛？答案是否定的揪利。如果部分同學對上文Floyd有一定疑惑的，此時正好可以講解狠持，為什么從i到j無非就是兩種走法呢疟位？就是因為源點在循環(huán)，假設現(xiàn)在有另一種最短的情況是 i可以先走到i2再走到k再走到j喘垂，需要經(jīng)過兩個中介點甜刻，那么顯然在i直接到k的路要比i走到i2再走到k的路要長，所以你才回選擇多走一個中介點嘛王污，這肯定是經(jīng)過了一次源點為i中介點為i2終點為k的循環(huán)罢吃。此時你獲得了一個方案1【i】【j】=【i】【k】+【k】【j】（其中【i】【k】=【i】【i2】+【i2】【k】經(jīng)過那次循環(huán)【i】【k】里的值得到了更新）。但這不是唯一方案哦昭齐，另一種方案2是【i】【j】=【i】【i2】+【i2】【j】（其中【i2】【j】=【i2】【k】+【k】【j】），看矾柜，就算是四個點兩種方案阱驾，但最終都變成了形如if(Chara[i][j] > Chara[i][k] + Chara[k][j])? Chara[i][j] = Chara[i][k] + Chara[k][j];的式子。所以無論怎么走最終都會只有兩種情況怪蔑，即Chara[i][j]和Chara[i][k] + Chara[k][j]里覆。 這個案例中因為要兩個中介點都經(jīng)過所以這兩種方案的最終值是相等的。
如果還是這四個點i缆瓣，i2喧枷，k，j弓坞，但這次我們的走法是i隧甚，i2，j不經(jīng)過k才是最短路徑渡冻，那么我們的方案應該是【i】【j】=【i】【i2】+【i2】【j】（【i2】【j】小于【i2】【k】+【k】【j】）這種方案我們單單去掉Floyd算法中的源點循環(huán)就會發(fā)生錯誤啦戚扳。因為，這里需要判斷【i2】【j】小于【i2】【k】+【k】【j】族吻，在Floyd中必然需要做一次源點為i2中介值為k終點為j的判斷帽借，但是我們單純的刪掉了源點的循環(huán)珠增，源點永遠在i永遠不會出現(xiàn)在i2的位置上，我們就會與這種方案失之交臂了砍艾。
所以我們不能單純的刪除源點的循環(huán)蒂教，而是要完善思路。
我們提出的改良方案就是在中介點的這個循環(huán)時脆荷，中介點不能是任取的凝垛。在Floyd中這個中介點可以說是任取的，因為我們直接按編號從1到n循環(huán)著來取得简烘，并沒有去考慮權(quán)值的問題苔严。改良的核心思路是（當然了學術史上Dijkstra并非Floyd的改良，這里是從學習者的角度看）按從源點i到其余每個頂點的最短路徑升序依次求出從源點到各頂點的最短路徑孤澎。也就是說現(xiàn)在循環(huán)這個中介點的順序必須是按距離源點的距離升序順序排列的届氢！接下來的操作就和Floyd類似了，下面請看代碼覆旭。
參數(shù)解釋
Chara數(shù)組 ：儲存兩點間的距離退子，Chara[i][j]的值就是點i到點j的距離。
dis數(shù)組：儲存起點到各個點的距離型将，dis[i]就是起點到i點的距離寂祥。
vis數(shù)組：標記點是否訪問過
INF：宏定義的最大值路不通
有兩個數(shù)組，dis和vis含義參見上面七兜，初始時vis中只有起點丸凭，更新dis中的起點到所有點的距離.
遍歷所有節(jié)點，找到距離起點最近的一個點K腕铸，將這個點加入vis中標記
進行松弛操作惜犀，遍歷沒有在vis數(shù)組中的其他所有點，比較起點——>該點和起點——>K點——>該點的距離狠裹，
重復2-3操作虽界，直到所有的點遍歷完
代碼
#define INF 65535
int n,m,s,t;
int Chara[N][N],dis[N],vis[N],p[i];
void Dijkstra(int src)? //src傳入的起點
{
? ? for(int i=0; i<m; i++) //初始化起點到所有點的距離
? ? {
? ? ? ? dis[i] = Chara[src][i];? //起始位置到i點的距離
? ? ? ? vis[i] = 0;//初始化visit
? ? ? ? p[i]=0;
? ? }
? ? dis[src] = 0; //到自身距離為0
? ? vis[src] = 1; //標記 注src=0
? ? for(int i=0; i<m; i++)//i為此二維表的層數(shù)（m個點最多m*m條路? i為m層）
? ? {
? ? ? ? int ans = INF,k;? //INF最大距離 表示不通
? ? ? ? for(int j=0; j<m; j++) // 尋找未被訪問過距離起點v0最近的點
? ? ? ? {
? ? ? ? ? ? if(!vis[j] && dis[j] < ans)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? k = j;
? ? ? ? ? ? ? ? ans = dis[j];
? ? ? ? ? ? }
? ? ? ? }//此點為K
? ? ? ? vis[k] = 1;? //標記已訪問
? ? ? ? if(ans == INF) break; //表示剩下所有點都不通
? ? ? ? for(int j =0; j<m; j++)? //松弛操作，更新起點到所有未訪問點的距離
? ? ? ? {//j為目標點（共有m列）
? ? ? ? ? ? if(!vis[j] &&? dis[k] + Chara[k][j]<dis[j] )
? ? ? ? ? ? {
? ? ? ? ? ? ? ? dis[j] = dis[k] + Chara[k][j];
? ? ? ? ? ? ? ? p[j]=k;//存放前驅(qū)節(jié)點
? ? ? ? ? ? }
? ? ? ? }
? ? }
}//最后這張表m行 每行一個點 行數(shù)越多的點距離越遠 即所謂升序排列涛菠。
