定義
Dijkstra算法一般的表述通常有兩種方式，一種用永久和臨時标号方式，一種是用OPEN, CLOSE表的方式，這裡均采用永久和臨時标号的方式。注意該算法要求圖中不存在負權邊。
原理
1.首先，引入一個輔助數組(vector)D，它的每個元素表示當前所找到的從起始點（即源點）到其它每個頂點的長度。
例如，表示從起始點到頂點3的路徑相對最小長度為2。這裡強調相對就是說在算法執行過程中D的值是在不斷逼近最終結果但在過程中不一定就等于長度。
2.D的初始狀态為：若從到有弧（即從到存在連接邊），則為弧上的權值（即為從到的邊的權值）；否則置為∞。
顯然，長度為的路徑就是從出發到頂點的長度最短的一條路徑，此路徑為。
3.那麼，下一條長度次短的是哪一條呢？也就是找到從源點到下一個頂點的最短路徑長度所對應的頂點，且這條最短路徑長度僅次于從源點到頂點的最短路徑長度。
假設該次短路徑的終點是，則可想而知，這條路徑要麼是，或者是。它的長度或者是從到的弧上的權值，或者是加上從到的弧上的權值。
4.一般情況下，假設S為已求得的從源點出發的最短路徑長度的頂點的集合，則可證明：下一條次最短路徑（設其終點為）要麼是弧，或者是從源點出發的中間隻經過S中的頂點而最後到達頂點的路徑。
因此，下一條長度次短的的最短路徑長度必是，其中要麼是弧上的權值，要麼是和弧上的權值之和。
算法描述如下：
1）令arcs表示弧上的權值。若弧不存在，則置arcs為∞（在本程序中為MAXCOST）。S為已找到的從出發的的終點的集合，初始狀态為空集。那麼，從出發到圖上其餘各頂點可能達到的長度的初值為；
2）選擇，使得；
3）修改從出發的到集合V-S中任一頂點的最短路徑長度。
問題描述
在有向圖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中頂點對應的距離值
若存在，d(V0,Vi)為弧上的權值
若不存在，d(V0,Vi)為∞
2.從T中選取一個與S中頂點有關聯邊且權值最小的頂點W，加入到S中
3.對其餘T中頂點的距離值進行修改：若加進W作中間頂點，從V0到Vi的距離值縮短，則修改此距離值
重複上述步驟2、3，直到S中包含所有頂點，即W=Vi為止。
算法實現
pascal語言
下面是該算法的Pascal程序
1
type
|
2
bool=array[1..10]ofboolean;
|
3
arr=array[0..10]ofinteger;
|
4
var
|
5
a:array[1..10,1..10]ofinteger;//存儲圖的鄰接數組，無邊為10000
|
6
c,d,e:arr;//c為最短路徑數值,d為各點前趨,
|
7
t:bool;//e：路徑，t為輔助數組
|
8
i,j,n,m:integer;
|
9
inf,outf:text;
|
10
procedure init;//不同題目鄰接數組建立方式不一樣
|
11
begin
|
12
assign(inf,inputfile);
|
13
assign(outf,outputfile);
|
14
reset(inf);
|
15
rewrite(outf);
|
16
read(inf,n);
|
17
for i:= 1 to n do
|
18
begin
|
19
for j := 1 to n do
|
20
begin
|
21
read(inf,a[i,j]);
|
22
if a[i,j]=0 then
|
23
a[i,j]:=10000;
|
24
end;
|
25
end;
|
26
end;
|
27
procedure dijkstra(qi:integer;t:bool;varc{,d}:arr);
|
28
//qi起點,{}中為求路徑部分,不需求路徑時可以不要
|
29
var
|
30
i,j,k,min:integer;
|
31
begin
|
32
t[qi]:=true;
|
33
//t數組一般在調用前初始,除起點外所有節點都化成false,也可将部分點初始化成true以回避這些點
|
34
for i:= 1 to n do
|
35
d[i] := qi;
|
36
d[qi]:=0;
|
37
for i:=1 to n do
|
38
c[i]:=a[qi,i];
|
39
for i:= 1 to n-1 do
|
40
begin
|
41
min:=maxint;//改為最大值
|
42
for j:=1 to n do
|
43
if(c[j]
|
44
begin
|
45
k:=j;
|
46
min:=c[j];
|
47
end;
|
48
t[k]:=true;
|
49
for j:=1 to n do
|
50
if(c[k]+a[k,j]
|
51
begin
|
52
c[j]:=c[k]+a[k,j];
|
53
d[j]:=k;
|
54
end;
|
55
end;
|
56
end;
|
57
|
58
procedure make(zh:integer;d:arr;vare:arr);//生成路徑,e[0]保存路徑
|
59
var
|
60
i,j,k:integer;//上的節點個數
|
61
begin
|
62
i:=0;
|
63
while d[zh]<>0 do
|
64
begin
|
65
inc(i);
|
66
e[i]:=zh;
|
67
zh:=d[zh];
|
68
end;
|
69
inc(i);
|
70
e[i]:=qi;
|
71
e[0]:=i;
|
72
end;
|
主程序調用：求長度：初始化t，然後dijkstra(qi,t,c,d)
求路徑：make(m,d,e)，m是終點
C語言
下面是該算法的C語言實現
1
#include
|
2
#include
|
3
#define max1 10000000 //原詞條這裡的值太大，導緻溢出，後面比較大小時會出錯
|
4
int a[1000][1000];
|
5
int d[1000];//d表示源節點到該節點的最小距離
|
6
int p[1000];//p标記訪問過的節點
|
7
int i, j, k;
|
8
int m;//m代表邊數
|
9
int n;//n代表點數
|
10
int main()
|
11
{
|
12
scanf("%d%d",&n,&m);
|
13
int min1;
|
14
int x,y,z;
|
15
for(i=1;i<=m;i++)
|
16
{
|
17
scanf("%d%d%d",&x,&y,&z);
|
18
a[x][y]=z;
|
19
a[y][x]=z;
|
20
}
|
21
for( i=1; i<=n; i++)
|
22
d[i]=max1;
|
23
d[1]=0;
|
24
for(i=1;i<=n;i++)
|
25
{
|
26
min1 = max1;
|
27
//下面這個for循環的功能類似冒泡排序，目的是找到未訪問節點中d[j]值最小的那個節點，
|
28
//作為下一個訪問節點，用k标記
|
29
for(j=1;j<=n;j++)
|
30
if(!p[j]&&d[j]
|
31
{
|
32
min1=d[j];
|
33
k=j;
|
34
}
|
35
//p[k]=d[k]; // 這是原來的代碼，用下一 條代碼替代。初始時，執行到這裡k=1，而d[1]=0
|
36
//從而p[1]等于0，這樣的話，上面的循環在之後的每次執行之後，k還是等于1。
|
37
p[k] = 1; //置1表示第k個節點已經訪問過了
|
38
for(j=1;j<=n;j++)
|
39
if(a[k][j]!=0&&!p[j]&&d[j]>d[k]+a[k][j])
|
40
d[j]=d[k]+a[k][j];
|
41
}
|
42
//最終輸出從源節點到其他每個節點的最小距離
|
43
for(i=1;i
|
44
printf("%d->",d[i]);
|
45
printf("%dn",d[n]);
|
46
return 0;
|
47
}
|
大學經典教材<<數據結構>>(C語言版 嚴蔚敏 吳為民 編著)中該算法的實現
1
/*
|
2
測試數據 教科書 P189 G6 的鄰接矩陣 其中 數字 1000000 代表無窮大
|
3
6
|
4
1000000 1000000 10 100000 30 100
|
5
1000000 1000000 5 1000000 1000000 1000000
|
6
1000000 1000000 1000000 50 1000000 1000000
|
7
1000000 1000000 1000000 1000000 1000000 10
|
8
1000000 1000000 1000000 20 1000000 60
|
9
1000000 1000000 1000000 1000000 1000000 1000000
|
10
結果：
|
11
D[0] D[1] D[2] D[3] D[4] D[5]
|
12
0 1000000 10 50 30 60
|
13
*/
|
14
#include
|
15
#include
|
16
#define MAX 1000000
|
17
using namespace std;
|
18
int arcs[10][10];//鄰接矩陣
|
19
int D[10];//保存最短路徑長度
|
20
int p[10][10];//路徑
|
21
int final[10];//若final[i] = 1則說明 頂點vi已在集合S中
|
22
int n = 0;//頂點個數
|
23
int v0 = 0;//源點
|
24
int v,w;
|
25
void ShortestPath_DIJ()
|
26
{
|
27
for (v = 0; v < n; v++) //循環 初始化
|
28
{
|
29
final[v] = 0; D[v] = arcs[v0][v];
|
30
for (w = 0; w < n; w++) p[v][w] = 0;//設空路徑
|
31
if (D[v] < MAX) {p[v][v0] = 1; p[v][v] = 1;}
|
32
}
|
33
D[v0] = 0; final[v0]=1; //初始化 v0頂點屬于集合S
|
34
//開始主循環 每次求得v0到某個頂點v的最短路徑 并加v到集合S中
|
35
for (int i = 1; i < n; i++)
|
36
{
|
37
int min = MAX;
|
38
for (w = 0; w < n; w++)
|
39
{
|
40
//我認為的核心過程--選點
|
41
if (!final[w]) //如果w頂點在V-S中
|
42
{
|
43
//這個過程最終選出的點 應該是選出當前V-S中與S有關聯邊
|
44
//且權值最小的頂點 書上描述為 當前離V0最近的點
|
45
if (D[w] < min) {v = w; min = D[w];}
|
46
}
|
47
}
|
48
final[v] = 1; //選出該點後加入到合集S中
|
49
for (w = 0; w < n; w++)//更新當前最短路徑和距離
|
50
{
|
51
/*在此循環中 v為當前剛選入集合S中的點
|
52
則以點V為中間點 考察 d0v+dvw 是否小于 D[w] 如果小于 則更新
|
53
比如加進點 3 則若要考察 D[5] 是否要更新 就 判斷 d(v0-v3) + d(v3-v5) 的和是否小于D[5]
|
54
*/
|
55
if (!final[w] && (min+arcs[v][w]
|
56
{
|
57
D[w] = min + arcs[v][w];
|
58
// p[w] = p[v];
|
59
p[w][w] = 1; //p[w] = p[v] + [w]
|
60
}
|
61
}
|
62
}
|
63
}
|
64
|
65
|
66
int main()
|
67
{
|
68
cin >> n;
|
69
for (int i = 0; i < n; i++)
|
70
{
|
71
for (int j = 0; j < n; j++)
|
72
{
|
73
cin >> arcs[i][j];
|
74
}
|
75
}
|
76
ShortestPath_DIJ();
|
77
for (int i = 0; i < n; i++) printf("D[%d] = %dn",i,D[i]);
|
78
return 0;
|
79
}
|
堆優化
思考
該算法複雜度為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代碼
1
//假設起點為src, 終點為dst, 圖以二維矩陣的形式存儲，若graph[i][j] == 0, 代表i,j不相連
|
2
//visit[i] == 0,代表未訪問,visit[0] == -1代表已訪問
|
3
public int Dijkstra(int src, int dst, int[][] graph,int[] visit){
|
4
//節點個數
|
5
int n = graph.length;
|
6
PriorityQueue pq = new PriorityQueue<>(new Node());
|
7
//将起點加入pq
|
8
pq.add(new Node(src, 0));
|
9
while (!pq.isEmpty()){
|
10
Node t = pq.poll();
|
11
//當前節點是終點，即可返回最短路徑
|
12
if(t.node == dst)
|
13
return t.cost;
|
14
//t節點表示還未訪問
|
15
if (visit[t.node]==0){
|
16
//将節點設置為已訪問
|
17
visit[t.node] = -1;
|
18
//将當前節點相連且未訪問的節點遍曆
|
19
for (int i = 0; i < n; i++) {
|
20
if (graph[t.node][i]!=0 && visit[i]==0) {
|
21
pq.add(new Node(i, t.cost + graph[t.node][i]));
|
22
}
|
23
}
|
24
}
|
25
}
|
26
return -1;
|
27
}
|
28
//定義一個存儲節點和離起點相應距離的數據結構
|
29
class Node implements Comparator {
|
30
public int node;
|
31
public int cost;
|
32
|
33
public Node(){}
|
34
|
35
public Node(int node, int cost){
|
36
this.node = node;
|
37
this.cost = cost;
|
38
}
|
39
@Override
|
40
public int compare(Node node1, Node node2){
|
41
return node1.cost-node2.cost;
|
42
}
|
43
}
|
上一篇：金蟲草三參膠囊
下一篇：時分複用技術
相關詞條
相關搜索
其它詞條
