有這樣一道題：在一個(gè)圖（如圖所示）中，一共有四個(gè)點(diǎn)：1 2 3 4

這四個(gè)點(diǎn)之間各有相連，且每條邊都有自己的權(quán)值。現(xiàn)在小明在點(diǎn)1上，

他想要到3去，請(qǐng)問最短路徑是多少。

---

---

很容易得到該圖的鄰接矩陣。我們建立一個(gè)二維數(shù)組a。a[i][j]，i表示
起點(diǎn)，為行，j表示終點(diǎn)，為列。將相應(yīng)的權(quán)值傳入其中，如果從一個(gè)
點(diǎn)到另一個(gè)點(diǎn)不通，就認(rèn)為其權(quán)值為無限

例如（1-》2）為2，則a[1][2]=2；
而因?yàn)?到1不通，就令a[2][1]=∞；
另外a[1][1]之類的起點(diǎn)終點(diǎn)相同的都設(shè)為了0；

對(duì)這種求點(diǎn)i到點(diǎn)j的最短路徑的問題，很難直接求得。通常是要多求一
些多余的量才能得到結(jié)果。因?yàn)槲覀儽仨氁龊帽闅v全圖的準(zhǔn)備才能比
較或是尋找出其最短路徑。

---

這時(shí)候我們來介紹兩種算法：

• 一種是Dijkstra算法單源最短路徑算法；
• 一種是Floyd多元路徑最短算法；

今天只說單源最短路徑算法
所謂單源，即求從一個(gè)點(diǎn)出發(fā)，到其他各點(diǎn)的最短路徑，也就是說
如果這個(gè)圖有n個(gè)點(diǎn)，我們要求n-1個(gè)路徑。
對(duì)一個(gè)圖G來說，它的點(diǎn)集為V，我們要做的就是求出從起點(diǎn)v到V中其
余各點(diǎn)的最短路徑。

首先介紹單源最短路徑的核心算法：
　起點(diǎn)是v，我們知道在整個(gè)圖中，以v為起點(diǎn)的路徑有很多條，有長的。有短的；有的簡單，只有一段弧，只有兩個(gè)點(diǎn)：起點(diǎn)。終點(diǎn)。有的復(fù)雜，有好幾段弧，起點(diǎn)終點(diǎn)之間隔了好幾個(gè)節(jié)點(diǎn)。
　我們要做的就是先找到所有這些從v引出的路徑中的最短的那一條（v，…，j1）。
　然后通過某種算法（下文中將會(huì)介紹）再找出僅長于最短路徑的次短路徑(v，…，j2)，找到以后，（注意：我們把每一次找到的次短路徑的終點(diǎn)記錄下來，如果下一次找尋的時(shí)候遇到以這些點(diǎn)為終點(diǎn)的路徑就忽略掉），再找下一條次短路徑，再找，再找……
　　這里有一個(gè)辨析：

按照上述步驟，我們依次找到了整張圖中（具有不同終點(diǎn)的）最短的幾條路徑： （v,…，j1） (v,…，j2) (v,…，j3) …… (v,…，j) ……

這里，如果我們稱圖中所有以v為起點(diǎn) 以j為終點(diǎn)的路徑為j族，那么我們每找到一條次短路徑 （v，…，j），這條路徑（v，…，j）一定是j族中最短的那條。
為什么呢？按照我們的找法，我們實(shí)際上是把整張圖里的所有以v為起點(diǎn)的路徑按照從短到長的順序排列起來，然后從第一條路徑開始往后檢索，如果我們從前到后查找時(shí)第一次遇到了以j為終點(diǎn)的路徑，記為路徑1，接下來往后，我們遇到的每一條屬于j族的路徑都忽略，從而我們得到了之前的序列。顯然路徑1就是j族中最短的那一條，也是我們的目標(biāo)路徑之一。

---

我們 所要求的是點(diǎn)v到其余各點(diǎn)的最短路徑，其余各點(diǎn)有n-1個(gè)，也就是說，我們有n-1個(gè)終點(diǎn)，對(duì)應(yīng)n-1個(gè)族。對(duì)每個(gè)族，都有一個(gè)對(duì)應(yīng)的最短路徑。我們要做的就是求出每個(gè)族的最短路徑。

之前說到，我們要把每一次找到的次短路徑的終點(diǎn)記錄下來，下一次遇到的時(shí)候就忽略掉，這可以保證最終的得到的序列都屬于不同的族，我們可以建立一個(gè)點(diǎn)集S,每找到一條次短路徑，就將其終點(diǎn)并入集合S中，下一次找尋路徑的時(shí)候拿終點(diǎn)與點(diǎn)集S對(duì)比，決定是否保留。

就這樣，每一次我們都找到一個(gè)以j為終點(diǎn)的最短路徑，而每一次的終點(diǎn)j又都不同，當(dāng)找了n-1次時(shí)，就完成了單源最短路徑查找。

---

我們已經(jīng)了解完了整體的思路，所以現(xiàn)在的關(guān)鍵性問題就是如何完成對(duì)次短路徑的查找。也就是上文中提到的某種算法，它到底是什么呢？

• 第一步：

  　　一個(gè)圖中有許多條路徑，我們現(xiàn)在在圖G中找到以v為起點(diǎn)的最短的那一條路徑（v，j）。顯然我們可以很容易的的發(fā)現(xiàn)，這條最短路徑一定是與起點(diǎn)v直接相連的弧，j是v的鄰結(jié)點(diǎn)。如圖所示；
  　　

• 第二步：
  　接下來，我們來找次短路徑，也就是以v為起點(diǎn)的下一條最短的路徑。如圖所示我們會(huì)發(fā)現(xiàn)，次短路徑要么是弧（v，k）（注：k是v相鄰的點(diǎn)，除j外），要么是弧（v，j，k）(k是j緊鄰的點(diǎn))。
  　這樣，我們通過比較可以求出最短的那一條路徑（v，k）;

然后我們就會(huì)猜想，如果按照第二步的做法一直重復(fù)下去，不就能依次找到次短路徑了嗎？
但是，事實(shí)上，當(dāng)我們嘗試之后會(huì)發(fā)現(xiàn)，隨著不斷地重復(fù)查找次短路徑的過程，我們不能單純的像第二次查找那樣，因?yàn)槊恳淮蔚牟檎叶紩?huì)衍生很多分支。使得查找變得復(fù)雜。

---

怎么解決這個(gè)問題呢？為了方便理解我引入了一個(gè)觀測域的概念。

首先看一些定義：

• 點(diǎn)集Ｖ　圖中所有點(diǎn)的集合
• 點(diǎn)集S 　已經(jīng)找到相應(yīng)最短路徑的終點(diǎn)集合
• 數(shù)組Ｄ［ｎ］　存儲(chǔ)觀測域內(nèi)能觀測到的最短路徑，算上起點(diǎn)一共ｎ個(gè)數(shù)值 。比如D[k]對(duì)應(yīng)在觀測域中能觀測到的，k族中的最短路徑。
• 鄰接矩陣ａ［ｎ］［ｎ］　　存儲(chǔ)著相應(yīng)的權(quán)值

如圖所示：剛開始時(shí)，我立足于ｖ點(diǎn)，觀測域?yàn)?#xff56;點(diǎn)的四周，即ｖ的所有鄰接點(diǎn)。由鄰接矩陣ａ，更新數(shù)組Ｄ。此時(shí)D中的數(shù)為（ｖ，ｋ）的權(quán)值（ｋ為ｖ的鄰接點(diǎn)）。
　

隨后，我在我觀測域中找尋最短的那一條路徑（ｖ，ｊ）也就是查找數(shù)組Ｄ中最小的數(shù)，并將ｊ收入集合Ｓ中。

如圖所示：現(xiàn)在我想找次短路徑，現(xiàn)在我清楚，這條次短路徑要么是（ｖ，ｋ）（ｋ為觀測域中的點(diǎn)，但不屬于Ｓ）的最短邊，要么是通過ｊ點(diǎn)的弧（ｖ，ｊ，ｋ）（ｋ為ｊ的鄰接點(diǎn)，但不屬于S）的最短邊。

我們干脆將ｊ的鄰接點(diǎn)全都納入觀測域，同時(shí)更新數(shù)組Ｄ，通過數(shù)組D找出次短邊（ｖ,ｊ），再將ｊ壓入S中。

不斷重復(fù)該步驟，直到所有的點(diǎn)都入了Ｓ，就完成了查找，這時(shí)數(shù)組D
Ｄ［ｋ］就是從ｖ到ｋ的最短路徑的長度。如果你想知道具體的路徑時(shí)只需加個(gè)棧就行了。

---

所以完整的步驟是這樣的：

• 第一步：
  初始化點(diǎn)集Ｓ，將起點(diǎn)ｖ收入Ｓ中。初始化數(shù)組Ｄ：Ｄ[k]=a[v][k];

• 第二步：找尋次短路徑。即查找數(shù)組D找出觀測域中最短路徑（v，j）：D[j]=min(D[k]|k不屬于S)。將j壓入點(diǎn)集S中

• 第三步：將j的鄰接點(diǎn)并入觀測域，即用j的鄰接點(diǎn)更新數(shù)組D：

  如果D[k]>D[j]+a[j][k] (k為j鄰接點(diǎn)，k不屬于S)令D[k]=D[j]+a[j][k]如果D[k]>D[j]+a[j][k] (k為j鄰接點(diǎn)，k不屬于S)就不做操作

然后不斷重復(fù)第二步和第三步直到找到全部節(jié)點(diǎn)為止。

具體實(shí)現(xiàn)為：

#include<iostream> using namespace std; #define BUTONG 1000000 // 無限大為不通 #define NUM 4 //d點(diǎn)數(shù)為4 int a[NUM][NUM]={0,2,6,4,BUTONG,0,3,BUTONG,7,BUTONG,0,1,5,BUTONG,12,0}; #define OK 1 #define ERROR 0 typedef int status;bool finish(bool *S,int n) //是否完成 找尋 {for(int i=0;i<n;i++){if(!S[i])return false;}return true; }status djs(int n,int t)//a 為數(shù)組 n 為點(diǎn)的個(gè)數(shù)，v為起始點(diǎn) {//初始化數(shù)組vint D[n];for(int i=0;i<n;i++)D[i]=a[t][i];D[t]=0;//初始化已訪問數(shù)集S;bool S[n];for(int i=0;i<n;i++)S[i]=false;S[t]=true;int j=0;int min=BUTONG;while (!finish(S,n)){ j=0;min=BUTONG;for(int i=0;i<n;i++) //找到觀測域中最短路徑（v,j） {if(S[i]) continue;if(min>D[i]) {min=D[i];j=i;} } S[j]=true; //將j納入點(diǎn)集S中 for(int i=0;i<n;i++) //更新觀測域 {if(S[i]) continue;if(D[i]>D[j]+a[j][i])D[i]=D[j]+a[j][i]; }}for(int i=0;i<n;i++) //輸出 {printf("最短路徑是（v,%d）長度是%d\n",i,D[i]);}return OK; } int main() {djs(NUM,1);return 0;}

總結(jié)

以上是生活随笔為你收集整理的单源最短路径---Dijkstra算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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