求最短路徑的算法很多，常見的有Dijkstra，Bellmen，F(xiàn)loyd等，他們原理和時間空間復(fù)雜度各有不同，其中最有代表性也比較好理解的就是Dijkstra算法。Chuck在百度面試時因為有過ACM經(jīng)歷所以被問到算法這部分，手寫了一段Dijkstra算法的實現(xiàn)。
Dijkstra算法適合處理稠密圖而且可以處理雙向圖，但缺點是不能處理帶有負邊權(quán)值的路徑問題。Dijkstra算法是基于貪心算法的一種實現(xiàn)，其運算過程也包含了動態(tài)規(guī)劃的思想，時間復(fù)雜度為O(n^2)。
其算法執(zhí)行過程不難理解，講解原理之前先定義如下變量。Dijkstra算法需要定義一個二維數(shù)組e[n][n]（n表示一共n個點），每個單元存放一個值，e[i][j]表示i點到j(luò)點的距離，e[i][i]的點距離均設(shè)為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
點與點之間不可到達時，其距離設(shè)為無窮大，以不干擾最短路徑的計算。
以試求1到6的最短路徑為例，將1設(shè)置為源點。以源點到各點的距離對dis[ ]和vis[ ]數(shù)組進行初始化。這一點很像動態(tài)規(guī)劃中對結(jié)果集的初始化過程，但還是略有區(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;
}
}
//設(shè)置該點已被訪問
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算法作為考點提問。
