迪杰斯特拉算法主要是產(chǎn)生從源點(diǎn)到其他點(diǎn)的最短路徑，換句話說(shuō)這些最短路徑也有著長(zhǎng)短的區(qū)別。

迪杰斯特拉算法的主要思路：

1.按照長(zhǎng)短依次來(lái)產(chǎn)生最短路徑。

2.并且在產(chǎn)生最短路徑的過(guò)程中，用現(xiàn)有最短的最短路徑來(lái)進(jìn)行松弛操作。

具體實(shí)現(xiàn)的方法：數(shù)據(jù)結(jié)構(gòu)：1個(gè)鄰接矩陣啊a[n][n]，1個(gè)一位數(shù)組dis[n]（用來(lái)存最短路徑），加上一個(gè)標(biāo)記數(shù)組flag[n](這個(gè)數(shù)組一定要有，已經(jīng)用來(lái)松弛過(guò)的邊就不能再使用了)。

大致流程：

1.首先一個(gè)for循環(huán)對(duì)dis數(shù)組進(jìn)行初始化。

2.緊接著一個(gè)for循環(huán)用來(lái)依次產(chǎn)生最短路徑，里面嵌套兩個(gè)for循環(huán)，一個(gè)用來(lái)找到當(dāng)前最短的最短路徑，下一個(gè)用來(lái)進(jìn)行松弛操作。

看個(gè)模板題：

hdu2544

Problem Description

在每年的校賽里，所有進(jìn)入決賽的同學(xué)都會(huì)獲得一件很漂亮的t-shirt。但是每當(dāng)我們的工作人員把上百件的衣服從商店運(yùn)回到賽場(chǎng)的時(shí)候，卻是非常累的！所以現(xiàn)在他們想要尋找最短的從商店到賽場(chǎng)的路線，你可以幫助他們嗎？

Input

輸入包括多組數(shù)據(jù)。每組數(shù)據(jù)第一行是兩個(gè)整數(shù)N、M（N<=100，M<=10000），N表示成都的大街上有幾個(gè)路口，標(biāo)號(hào)為1的路口是商店所在地，標(biāo)號(hào)為N的路口是賽場(chǎng)所在地，M則表示在成都有幾條路。N=M=0表示輸入結(jié)束。接下來(lái)M行，每行包括3個(gè)整數(shù)A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A與路口B之間有一條路，我們的工作人員需要C分鐘的時(shí)間走過(guò)這條路。 輸入保證至少存在1條商店到賽場(chǎng)的路線。

Output

對(duì)于每組輸入，輸出一行，表示工作人員從商店走到賽場(chǎng)的最短時(shí)間。

Sample Input

2 1

1 2 3

3 3

1 2 5

2 3 5

3 1 2

0 0

Sample Output

3

2

代碼：

#include <iostream>
#define  INF 99999999
#include <string.h>
using namespace std;

int a[110][110],dis[110],flag[110];

void dijkstra(int n,int start){
    for(int i=1;i<=n;i++){
      dis[i]=a[start][i];
    }
    int minl,tmp;
    memset(flag,0,sizeof(flag));
    for(int i=2;i<=n;i++){
    minl=INF;
    for(int j=2;j<=n;j++){
        if(dis[j]<minl&&flag[j]==0){
          minl=dis[j];
          tmp=j;
        }
    }
    for(int j=2;j<=n;j++){
    if(dis[tmp]+a[tmp][j]<dis[j])
      dis[j]=dis[tmp]+a[tmp][j];
    }
    flag[tmp]=1;
    }
}

int main(){
    int n,m;
    int x,y,path;
    while(cin>>n>>m&&n!=0&&m!=0){
    for(int i=1;i<=n;i++)
       for(int j=1;j<=n;j++){
          if(i!=j)
          a[i][j]=INF;
          else
          a[i][j]=0;
       }
    for(int i=1;i<=m;i++){
      cin>>x>>y>>path;
      a[x][y]=a[y][x]=path;
    }
    dijkstra(n,1);
    cout<<dis[n]<<endl;
    }
    return 0;
}

補(bǔ)充：

迪杰斯特拉算法是A*算法的最簡(jiǎn)單版本（無(wú)啟發(fā)式函數(shù)），也是我們常說(shuō)的一致代價(jià)搜索。

迪杰斯特拉算法最好采用優(yōu)先隊(duì)列的形式來(lái)實(shí)現(xiàn)，方便后面進(jìn)行各種改進(jìn)。

總結(jié)

以上是生活随笔為你收集整理的迪杰斯特拉算法简单分析的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。