基本介紹
- 中文名:迪克斯特拉算法
- 外文名:Dijkstra's Algorithm
- 分類:計算機算法
- 用途:單源最短路徑問題
定義,原理,問題描述,算法思想,算法實現,pascal語言,C語言,堆最佳化,思考,實現,Java代碼,
定義
Dijkstra算法一般的表述通常有兩種方式,一種用永久和臨時標號方式,一種是用OPEN, CLOSE表的方式,這裡均採用永久和臨時標號的方式。注意該算法要求圖中不存在負權邊。
原理
例如,D[3] = 2表示從起始點到頂點3的路徑相對最小長度為2。這裡強調相對就是說在算法執行過程中D的值是在不斷逼近最終結果但在過程中不一定就等於長度。
2.D的初始狀態為:若從
到
有弧(即從
到
存在連線邊),則D
為弧上的權值(即為從
到
的邊的權值);否則置D
為∞。
![](/img/4/caa/299ed82ed158edbd64698baf1a2c.jpg)
![](/img/d/bc3/fc31b0b12c989fbb3213bba8c044.jpg)
![](/img/4/caa/299ed82ed158edbd64698baf1a2c.jpg)
![](/img/d/bc3/fc31b0b12c989fbb3213bba8c044.jpg)
![](/img/c/460/7be9db83d66f1c227c733e682545.jpg)
![](/img/4/caa/299ed82ed158edbd64698baf1a2c.jpg)
![](/img/d/bc3/fc31b0b12c989fbb3213bba8c044.jpg)
![](/img/c/460/7be9db83d66f1c227c733e682545.jpg)
顯然,長度為 D
= Min{ D |
∈V } 的路徑就是從
出發到頂點
的長度最短的一條路徑,此路徑為(
)。
![](/img/5/dab/7c2030cca574f90b09c9d9be768e.jpg)
![](/img/d/bc3/fc31b0b12c989fbb3213bba8c044.jpg)
![](/img/4/caa/299ed82ed158edbd64698baf1a2c.jpg)
![](/img/2/c9e/230d72961fc836bfd4271628a7f8.jpg)
![](/img/4/f4f/a5fa7960ba1b3abef8671df9656d.jpg)
3.那么,下一條長度次短的是哪一條呢?也就是找到從源點
到下一個頂點的最短路徑長度所對應的頂點,且這條最短路徑長度僅次於從源點
到頂點
的最短路徑長度。
![](/img/4/caa/299ed82ed158edbd64698baf1a2c.jpg)
![](/img/4/caa/299ed82ed158edbd64698baf1a2c.jpg)
![](/img/2/c9e/230d72961fc836bfd4271628a7f8.jpg)
假設該次短路徑的終點是
,則可想而知,這條路徑要么是(
),或者是(
)。它的長度或者是從
到
的弧上的權值,或者是D
加上從
到
的弧上的權值。
![](/img/d/ab1/79abe92e52114381dea583a2d90f.jpg)
![](/img/9/565/ce8525bcc50196ce37a8b537890a.jpg)
![](/img/2/6ac/af2fd59fbb8a1f2cb69581b8e87e.jpg)
![](/img/4/caa/299ed82ed158edbd64698baf1a2c.jpg)
![](/img/d/ab1/79abe92e52114381dea583a2d90f.jpg)
![](/img/5/dab/7c2030cca574f90b09c9d9be768e.jpg)
![](/img/b/a8e/80557460a1ba00e7e44a3119be0a.jpg)
![](/img/d/ab1/79abe92e52114381dea583a2d90f.jpg)
4.一般情況下,假設S為已求得的從源點
出發的最短路徑長度的頂點的集合,則可證明:下一條次最短路徑(設其終點為
)要么是弧(
),或者是從源點
出發的中間只經過S中的頂點而最後到達頂點
的路徑。
![](/img/4/caa/299ed82ed158edbd64698baf1a2c.jpg)
![](/img/d/60a/5ddec69e48e68dc5018579342864.jpg)
![](/img/9/375/6c25625000ffa8ef77340dbe6dbb.jpg)
![](/img/4/caa/299ed82ed158edbd64698baf1a2c.jpg)
![](/img/d/60a/5ddec69e48e68dc5018579342864.jpg)
因此,下一條長度次短的的最短路徑長度必是D
= Min{ D
|
∈V-S },其中D
要么是弧(
)上的權值,要么是D
(
∈S)和弧(
,
)上的權值之和。
![](/img/5/dab/7c2030cca574f90b09c9d9be768e.jpg)
![](/img/c/460/7be9db83d66f1c227c733e682545.jpg)
![](/img/d/bc3/fc31b0b12c989fbb3213bba8c044.jpg)
![](/img/c/460/7be9db83d66f1c227c733e682545.jpg)
![](/img/f/244/34660363643df0fba038d4c784db.jpg)
![](/img/b/671/20d8d267288de9e120e576aac314.jpg)
![](/img/d/ab1/79abe92e52114381dea583a2d90f.jpg)
![](/img/d/ab1/79abe92e52114381dea583a2d90f.jpg)
![](/img/d/bc3/fc31b0b12c989fbb3213bba8c044.jpg)
算法描述如下:
1)令arcs表示弧上的權值。若弧不存在,則置arcs為∞(在本程式中為MAXCOST)。S為已找到的從
出發的的終點的集合,初始狀態為空集。那么,從
出發到圖上其餘各頂點
可能達到的長度的初值為D=arcs[Locate Vex(G,
)],
∈V;
![](/img/4/caa/299ed82ed158edbd64698baf1a2c.jpg)
![](/img/4/caa/299ed82ed158edbd64698baf1a2c.jpg)
![](/img/d/bc3/fc31b0b12c989fbb3213bba8c044.jpg)
![](/img/d/bc3/fc31b0b12c989fbb3213bba8c044.jpg)
![](/img/d/bc3/fc31b0b12c989fbb3213bba8c044.jpg)
2)選擇
,使得D
=Min{ D |
∈V-S } ;
![](/img/2/c9e/230d72961fc836bfd4271628a7f8.jpg)
![](/img/5/dab/7c2030cca574f90b09c9d9be768e.jpg)
![](/img/d/bc3/fc31b0b12c989fbb3213bba8c044.jpg)
3)修改從
出發的到集合V-S中任一頂點
的最短路徑長度。
![](/img/4/caa/299ed82ed158edbd64698baf1a2c.jpg)
![](/img/d/ab1/79abe92e52114381dea583a2d90f.jpg)
問題描述
在有向圖 G=(V,E) 中,假設每條邊 E[i] 的長度為 w[i],找到由頂點 V0 到其餘各點的最短值。
算法思想
按路徑長度遞增次序產生算法:
把頂點集合V分成兩組:
(1)S:已求出的頂點的集合(初始時只含有源點V0)
(2)V-S=T:尚未確定的頂點集合
將T中頂點按遞增的次序加入到S中,保證:
(1)從源點V0到S中其他各頂點的長度都不大於從V0到T中任何頂點的最短路徑長度
(2)每個頂點對應一個距離值
S中頂點:從V0到此頂點的長度
T中頂點:從V0到此頂點的只包括S中頂點作中間頂點的最短路徑長度
依據:可以證明V0到T中頂點Vk的,或是從V0到Vk的直接路徑的權值;或是從V0經S中頂點到Vk的路徑權值之和
(反證法可證)
求最短路徑步驟
算法步驟如下:
G={V,E}
1. 初始時令 S={V0},T=V-S={其餘頂點},T中頂點對應的距離值
若存在<V0,Vi>,d(V0,Vi)為<V0,Vi>弧上的權值
若不存在<V0,Vi>,d(V0,Vi)為∞
2. 從T中選取一個與S中頂點有關聯邊且權值最小的頂點W,加入到S中
3. 對其餘T中頂點的距離值進行修改:若加進W作中間頂點,從V0到Vi的距離值縮短,則修改此距離值
重複上述步驟2、3,直到S中包含所有頂點,即W=Vi為止
算法實現
pascal語言
下面是該算法的Pascal程式
typebool=array[1..10]ofboolean;arr=array[0..10]ofinteger;vara:array[1..10,1..10]ofinteger;//存儲圖的鄰接數組,無邊為10000c,d,e:arr;//c為最短路徑數值,d為各點前趨,t:bool;//e:路徑,t為輔助數組i,j,n,m:integer;inf,outf:text;procedure init;//不同題目鄰接數組建立方式不一樣begin assign(inf,inputfile); assign(outf,outputfile); reset(inf); rewrite(outf); read(inf,n); for i:= 1 to n do begin for j := 1 to n do begin read(inf,a[i,j]); if a[i,j]=0 then a[i,j]:=10000; end; end; end;procedure dijkstra(qi:integer;t:bool;varc{,d}:arr);//qi起點,{}中為求路徑部分,不需求路徑時可以不要vari,j,k,min:integer;begin t[qi]:=true;//t數組一般在調用前初始,除起點外所有節點都化成false,也可將部分點初始化成true以迴避這些點 for i:= 1 to n do d[i] := qi; d[qi]:=0; for i:=1 to n do c[i]:=a[qi,i]; for i:= 1 to n-1 do begin min:=maxint;//改為最大值 for j:=1 to n do if(c[j]<min) and not t[j] then begin k:=j; min:=c[j]; end; t[k]:=true; for j:=1 to n do if(c[k]+a[k,j]<c[j]) and not t[j] then begin c[j]:=c[k]+a[k,j]; d[j]:=k; end; end;end; procedure make(zh:integer;d:arr;vare:arr);//生成路徑,e[0]保存路徑vari,j,k:integer;//上的節點個數begin i:=0; while d[zh]<>0 do begin inc(i); e[i]:=zh; zh:=d[zh]; end; inc(i); e[i]:=qi; e[0]:=i;end;
主程式調用:求長度:初始化t,然後dijkstra(qi,t,c,d)
求路徑:make(m,d,e) ,m是終點
C語言
下面是該算法的C語言實現
#include<stdio.h>#include<stdlib.h>#define max1 10000000 //原詞條這裡的值太大,導致溢出,後面比較大小時會出錯int a[1000][1000];int d[1000];//d表示源節點到該節點的最小距離int p[1000];//p標記訪問過的節點int i, j, k;int m;//m代表邊數int n;//n代表點數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循環的功能類似冒泡排序,目的是找到未訪問節點中d[j]值最小的那個節點, //作為下一個訪問節點,用k標記 for(j=1;j<=n;j++) if(!p[j]&&d[j]<min1) { min1=d[j]; k=j; } //p[k]=d[k]; // 這是原來的代碼,用下一 條代碼替代。初始時,執行到這裡k=1,而d[1]=0 //從而p[1]等於0,這樣的話,上面的循環在之後的每次執行之後,k還是等於1。 p[k] = 1; //置1表示第k個節點已經訪問過了 for(j=1;j<=n;j++) if(a[k][j]!=0&&!p[j]&&d[j]>d[k]+a[k][j]) d[j]=d[k]+a[k][j]; } //最終輸出從源節點到其他每個節點的最小距離 for(i=1;i<n;i++) printf("%d->",d[i]); printf("%d\n",d[n]); return 0;}
大學經典教材<<數據結構>>(C語言版 嚴蔚敏 吳為民 編著) 中該算法的實現
/*測試數據 教科書 P189 G6 的鄰接矩陣 其中 數字 1000000 代表無窮大61000000 1000000 10 100000 30 1001000000 1000000 5 1000000 1000000 10000001000000 1000000 1000000 50 1000000 10000001000000 1000000 1000000 1000000 1000000 101000000 1000000 1000000 20 1000000 601000000 1000000 1000000 1000000 1000000 1000000結果:D[0] D[1] D[2] D[3] D[4] D[5] 0 1000000 10 50 30 60*/#include <iostream>#include <cstdio>#define MAX 1000000using namespace std;int arcs[10][10];//鄰接矩陣int D[10];//保存最短路徑長度int p[10][10];//路徑int final[10];//若final[i] = 1則說明 頂點vi已在集合S中int n = 0;//頂點個數int v0 = 0;//源點int v,w;void ShortestPath_DIJ(){ for (v = 0; v < n; v++) //循環 初始化 { final[v] = 0; D[v] = arcs[v0][v]; for (w = 0; w < n; w++) p[v][w] = 0;//設空路徑 if (D[v] < MAX) {p[v][v0] = 1; p[v][v] = 1;} } D[v0] = 0; final[v0]=1; //初始化 v0頂點屬於集合S //開始主循環 每次求得v0到某個頂點v的最短路徑 並加v到集合S中 for (int i = 1; i < n; i++) { int min = MAX; for (w = 0; w < n; w++) { //我認為的核心過程--選點 if (!final[w]) //如果w頂點在V-S中 { //這個過程最終選出的點 應該是選出當前V-S中與S有關聯邊 //且權值最小的頂點 書上描述為 當前離V0最近的點 if (D[w] < min) {v = w; min = D[w];} } } final[v] = 1; //選出該點後加入到合集S中 for (w = 0; w < n; w++)//更新當前最短路徑和距離 { /*在此循環中 v為當前剛選入集合S中的點 則以點V為中間點 考察 d0v+dvw 是否小於 D[w] 如果小於 則更新 比如加進點 3 則若要考察 D[5] 是否要更新 就 判斷 d(v0-v3) + d(v3-v5) 的和是否小於D[5] */ if (!final[w] && (min+arcs[v][w]<D[w])) { D[w] = min + arcs[v][w]; // p[w] = p[v]; p[w][w] = 1; //p[w] = p[v] + [w] } } }}int main(){ cin >> n; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> arcs[i][j]; } } ShortestPath_DIJ(); for (int i = 0; i < n; i++) printf("D[%d] = %d\n",i,D[i]); return 0;}
堆最佳化
思考
該算法複雜度為n^2,我們可以發現,如果邊數遠小於n^2,對此可以考慮用堆這種數據結構進行最佳化,取出最短路徑的複雜度降為O(1);每次調整的複雜度降為O(elogn);e為該點的邊數,所以複雜度降為O((m+n)logn)。
實現
1. 將源點加入堆,並調整堆。
2. 選出堆頂元素u(即代價最小的元素),從堆中刪除,並對堆進行調整。
3. 處理與u相鄰的,未被訪問過的,滿足三角不等式的頂點
1):若該點在堆里,更新距離,並調整該元素在堆中的位置。
2):若該點不在堆里,加入堆,更新堆。
4. 若取到的u為終點,結束算法;否則重複步驟2、3。
Java代碼
//visit初始為0,防止回溯int visit[] = new int[n+1];//假設起點為src, 終點為dst, 圖以二維矩陣的形式存儲,若graph[i][j] == 0, 代表i,j不相連int Dijkstra(int src, int dst, int[][] graph){ PriorityQueue<Node> pq = new PriorityQueue<Node>(); //將起點加入pq pq.add(new Node(src, 0)); while(pq.size()){ Node t = pq.poll(); //當前節點是終點,即可返回最短路徑 if(t.node == dst) return t.cost; //若當前節點已遍歷過,跳過當前節點 if(visit[t.node]) continue; //將當前節點標記成已遍歷 visit[t.node] = 1; for(int i = 0; i < n; i++){ if(graph[t.node][i] && !visited[i]){ pq.add(new Node(i, t.cost + graph[t.node][i])); } } } return -1}//定義一個存儲節點和離起點相應距離的數據結構class Node implements Comparator<Node> { public int node; public int cost; public Node() { } public Node(int node, int cost) { this.node = node; this.cost = cost; } @Override public int compare(Node node1, Node node2) { if (node1.cost < node2.cost) return -1; if (node1.cost > node2.cost) return 1; return 0; }}