求最短路徑的算法很多，常見的有Dijkstra，Bellmen尤溜，F(xiàn)loyd等倔叼，他們原理和時間空間復雜度各有不同，其中最有代表性也比較好理解的就是Dijkstra算法宫莱。Chuck在百度面試時因為有過ACM經(jīng)歷所以被問到算法這部分丈攒，手寫了一段Dijkstra算法的實現(xiàn)。
Dijkstra算法適合處理稠密圖而且可以處理雙向圖授霸，但缺點是不能處理帶有負邊權值的路徑問題巡验。Dijkstra算法是基于貪心算法的一種實現(xiàn)，其運算過程也包含了動態(tài)規(guī)劃的思想碘耳，時間復雜度為O(n^2)显设。
其算法執(zhí)行過程不難理解，講解原理之前先定義如下變量辛辨。Dijkstra算法需要定義一個二維數(shù)組e[n][n]（n表示一共n個點）敷硅，每個單元存放一個值，e[i][j]表示i點到j點的距離愉阎，e[i][i]的點距離均設為0（自己到自己距離為0）绞蹦，還需要一個一維數(shù)組dis[n]，來記錄起始點到每個點的最短路徑榜旦，輸出時輸出dis[終點]即可幽七，此外還需要定義一個vis[n]數(shù)組用來統(tǒng)計每個點是否用到過。
通過一個例子溅呢，Chuck帶大家推理一下Dijkstra算法的計算過程：
現(xiàn)在給出幾條邊的值澡屡，求a到b點的最短路徑：
start end weight
1 2 1
1 3 12
2 3 9
2 4 3
4 3 4
4 5 13
5 6 4
4 6 15
3 5 5
根據(jù)所給數(shù)據(jù)填入二維數(shù)組e中，填入后數(shù)組e的情況為：
1 2 3 4 5 6
1 0 1 12 max max max
2 max 0 9 3 max max
3 max max 0 max 5 max
4 max max 4 0 13 15
5 max max max max 0 4
6 max max max max max 0
點與點之間不可到達時咐旧，其距離設為無窮大驶鹉，以不干擾最短路徑的計算。
以試求1到6的最短路徑為例铣墨，將1設置為源點室埋。以源點到各點的距離對dis[ ]和vis[ ]數(shù)組進行初始化。這一點很像動態(tài)規(guī)劃中對結果集的初始化過程伊约，但還是略有區(qū)別姚淆。初始化后的數(shù)組狀態(tài)：
dis 1 2 3 4 5 6
0 1 12 max max max
----------------------------------------------
//‘1’代表訪問過，‘0’表示尚未訪問
vis 1 2 3 4 5 6
1 0 0 0 0 0
第一步：尋找除1點外離源點最近的點并求以這個點為起點的邊到其他個點的距離屡律。通過dis[ ]數(shù)組可知腌逢，現(xiàn)在2點離1點最近，看以2為起點的邊2——>3超埋，2——>4搏讶。目前dis[3]=12佳鳖，而若從1先到2再從2到3距離則為dis[2]+e[2][3]=10<dis[3]！因此更新dis[3]的值媒惕。dis[4]現(xiàn)在為max腋颠，從1到2再到4距離為dis[2]+e[2][4]<dis[4]，因此更新dis[4]吓笙！得到新的dis[]數(shù)組為：
dis 1 2 3 4 5 6
0 1 10 4 max max
----------------------------------------------
//‘1’代表訪問過，‘0’表示尚未訪問
vis 1 2 3 4 5 6
1 1 0 0 0 0
第二步：再尋找3,4,5,6中距離源點最近的點巾腕。此時4離源點最近還按照剛才的做法4——>3面睛，4——>5，4——>6尊搬。dis[3]更新為dis[4]+e[4][3]=8叁鉴；dis[5]=dis[4]+e[4][5]=17；dis[6]=dis[4]+e[4][6]=19佛寿。此時數(shù)組變?yōu)椋?/p>
dis 1 2 3 4 5 6
0 1 8 4 17 19
----------------------------------------------
//‘1’代表訪問過幌墓，‘0’表示尚未訪問
vis 1 2 3 4 5 6
1 1 0 1 0 0
第三步：從3,5,6中找離源點最近的點為3。3出發(fā)3——>5冀泻。dis[5]>dis[3]+e[3][5]常侣，dis[5]更新為13。
dis 1 2 3 4 5 6
0 1 8 4 13 19
----------------------------------------------
//‘1’代表訪問過弹渔，‘0’表示尚未訪問
vis 1 2 3 4 5 6
1 1 1 1 0 0
第四步：5,6中5距離原點更近胳施，5出發(fā)5——>6，dis[6]>dis[5]+e[5][6]肢专，dis[6]變?yōu)?7舞肆。
dis 1 2 3 4 5 6
0 1 8 4 13 17
----------------------------------------------
//‘1’代表訪問過，‘0’表示尚未訪問
vis 1 2 3 4 5 6
1 1 1 1 1 0
第五步：只剩6了博杖，從6無出發(fā)路線故無法操作椿胯，dis[ ]最終定為：
dis 1 2 3 4 5 6
0 1 8 4 13 17
----------------------------------------------
//‘1’代表訪問過，‘0’表示尚未訪問
vis 1 2 3 4 5 6
1 1 1 1 1 1
從源點1到終點6的距離即為dis[6] = 17剃根。當然了哩盲，根據(jù)題目不同源點終點，題目求解方式略有不同但萬變不離其宗狈醉。接下來考慮代碼實現(xiàn)：
#include <iostream>
#include<stdio.h>
#define Max 9999999
using namespace std;
int dis[1005],vis[1005];
int e[1005][1005];
int n,m,a,b,u,v,w,Min;
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
if(n==0&&m==0) break;
for(int i=1;i<=n;i++)
{
vis[i]=0;
for(int j=1;j<=n;j++)
{
e[i][j]=Max;
}
}
//將邊輸入數(shù)組e
while(m--)
{
scanf("%d%d%d",&u,&v,&w);
if(e[u][v]>w)
{
e[u][v]=e[v][u]=w;
}
}
scanf("%d%d",&a,&b);
//初始化vis[ ]和dis[ ]
vis[a]=1;
for(int i=1;i<=n;i++)
{
dis[i]=e[a][i];
}
//Dijkstra方法核心代碼
for(int i=1;i<=n-1;i++)
{
//求距離源點最近的且未訪問過的點
Min=Max;
for(int j=1;j<=n;j++)
{
if(vis[j]==0&&dis[j]<Min)
{
Min=dis[j];u=j;
}
}
//設置該點已被訪問
vis[u]=1;
//更新從該點到其余各點的最短距離
for(v=1;v<=n;v++)
{
if(e[u][v]<Max)
{
if(dis[v]>dis[u]+e[u][v])
{
dis[v]=dis[u]+e[u][v];
}
}
}
}
printf("%d %d\n",dis[b],value[b]);
}
return 0;
}
Dijkstra算法在眾多算法中相對好理解种冬，如果理解其原理，完全可以在面試現(xiàn)場一邊推一邊寫舔糖。Dijkstra算法運用也很廣娱两，所以大企業(yè)的面試官如果問到這部分一般都會選擇Dijkstra算法作為考點提問。
