最短路徑(Dijkstra算法)

人有一個特點，一個字就是懶，縱觀世界上的交通發(fā)展史，從步行到馬車，再到自行車，汽車，再到飛機、輪船火箭，歸咎到底就是人想要更快更便捷的到達自己想去的地方，除了交通工具的升級，當然人們也在探索“最短路徑”，最短路徑問題是組合優(yōu)化領域的經(jīng)典問題之一，他廣泛用于計算機科學、交通工程、通信工程等領域。

在進行了離散數(shù)學的學習之后我又去查閱了迪杰斯特拉（Dijkstra）算法的資料，Dijkstra算法是由荷蘭科學家迪克斯特拉在1959年提出，從一個頂點到其余各頂點的最短路徑算法，主要特點是以起始點為中心向外層層擴展，直到擴展到終點。

Dijkstra算法具體的原理我將從一個實際問題出發(fā)來解釋。

假設我放假要出去玩，我發(fā)誓要逛遍所有日照市的海洋公園、海濱公園、香河公園、興海公園，但是我必須先去海洋公園或者海濱公園，因為他倆太搶手，然后再從海洋公園去香河公園，或興海公園，但是由于今天修路，海洋公園到興海公園的路沒了，通過這些需求，我在百度地圖畫了畫路線，是這樣子的：

地圖

通過簡化得到醬紫的圖像：

線圖

對圖像進行標準化并剔除海濱公園到香河公園較長的路線，經(jīng)過美化得到如下圖：

簡化美化圖

接下來問題就轉(zhuǎn)換成了從“1”分別到“2”，“3”，“4”，“5”的最短路徑，首先我們先用數(shù)據(jù)結(jié)構(gòu)存儲圖的信息：

我們還需要一個一維數(shù)組"arr"來存儲“1”號頂點到其余各個頂點的初始路程，即：

通過上述表格我們發(fā)現(xiàn)由“1”到“2”和“3”分別是3.9和6.5最近的是點“2”,因此點“2”確定：

接下來從“2”發(fā)現(xiàn)到“3”最近，因此“3”點確定：

即：

接下來從"3"到"4"和"5"發(fā)現(xiàn)"4"較近即"4"確定：

即：

最后從“4”到“5”：

即Dijkstra算法算是貪心算法實現(xiàn)的，首先把起點到所有點的距離存下來找個最短的，然后松弛一次再找出最短的，所謂的松弛操作就是，遍歷一遍看通過剛剛找到的距離最短的點作為中轉(zhuǎn)站會不會更近，如果更近了就更新距離，這樣把所有的點找遍之后就存下了起點到其他所有點的最短距離。

來自百度百科代碼實現(xiàn)：

#include

#include

#define max1 10000000  //原詞條這里的值太大，導致溢出，后面比較大小時會出錯

int a[1000][1000];

int d[1000];//d表示源節(jié)點到該節(jié)點的最小距離

int p[1000];//p標記訪問過的節(jié)點

int i, j, k;

int m;//m代表邊數(shù)

int n;//n代表點數(shù)

int main()

{

    scanf("%d%d",&n,&m);

    int    min1;

    int    x,y,z;

    for(i=1;i<=m;i++)

    {

        scanf("%d%d%d",&x,&y,&z);

        a[x][y]=z;

        a[y][x]=z;

    }

    for( i=1; i<=n; i++)

        d[i]=max1;

    d[1]=0;

    for(i=1;i<=n;i++)

    {

        min1 = max1;

        //下面這個for循環(huán)的功能類似冒泡排序，目的是找到未訪問節(jié)點中d[j]值最小的那個節(jié)點，

        //作為下一個訪問節(jié)點，用k標記

        for(j=1;j<=n;j++)

            if(!p[j]&&d[j]d[k]+a[k][j])

                d[j]=d[k]+a[k][j];

    }

    //最終輸出從源節(jié)點到其他每個節(jié)點的最小距離

    for(i=1;i",d[i]);

    printf("%d\n",d[n]); 

    return 0;

}