-
迪克斯特拉算法
鎖定
- 分 類
- 計算機算法 [1]
- 用 途
- 單源最短路徑問題 [1]
- 簡 稱
- Dij算法 [1]
迪克斯特拉算法定義
Dijkstra算法一般的表述通常有兩種方式，一種用永久和臨時標號方式，一種是用OPEN, CLOSE表的方式，這裏均採用永久和臨時標號的方式。注意該算法要求圖中不存在負權邊。
[2]
迪克斯特拉算法原理
4.一般情況下，假設S為已求得的從源點
出發的最短路徑長度的頂點的集合，則可證明：下一條次最短路徑（設其終點為
）要麼是弧(
)，或者是從源點
出發的中間只經過S中的頂點而最後到達頂點
的路徑。
[1]
算法描述如下：
1）令arcs表示弧上的權值。若弧不存在，則置arcs為∞（在本程序中為MAXCOST）。S為已找到的從
出發的的終點的集合，初始狀態為空集。那麼，從
出發到圖上其餘各頂點
可能達到的長度的初值為D=arcs[Locate Vex(G,
)]，
∈V；
[1]
迪克斯特拉算法問題描述
在有向圖 G=(V,E) 中，假設每條邊 E[i] 的長度為 w[i]，找到由頂點 V0 到其餘各點的最短值。
[1]
迪克斯特拉算法算法思想
按路徑長度遞增次序產生算法：
[1]
（反證法可證）
G={V,E}
迪克斯特拉算法算法實現
pascal語言
下面是該算法的Pascal程序
type
bool=array[1..10]ofboolean;
arr=array[0..10]ofinteger;
var
a:array[1..10,1..10]ofinteger;//存儲圖的鄰接數組，無邊為10000
c,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起點,{}中為求路徑部分,不需求路徑時可以不要
var
i,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]保存路徑
var
i,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;
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;
}
/*
測試數據 教科書 P189 G6 的鄰接矩陣 其中 數字 1000000 代表無窮大
6
1000000 1000000 10 100000 30 100
1000000 1000000 5 1000000 1000000 1000000
1000000 1000000 1000000 50 1000000 1000000
1000000 1000000 1000000 1000000 1000000 10
1000000 1000000 1000000 20 1000000 60
1000000 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 1000000
using 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)。
[2]
實現
Java代碼
//假設起點為src, 終點為dst, 圖以二維矩陣的形式存儲，若graph[i][j] == 0, 代表i,j不相連
//visit[i] == 0,代表未訪問,visit[0] == -1代表已訪問
public int Dijkstra(int src, int dst, int[][] graph,int[] visit){
//節點個數
int n = graph.length;
PriorityQueue<Node> pq = new PriorityQueue<>(new Node());
//將起點加入pq
pq.add(new Node(src, 0));
while (!pq.isEmpty()){
Node t = pq.poll();
//當前節點是終點，即可返回最短路徑
if(t.node == dst)
return t.cost;
//t節點表示還未訪問
if (visit[t.node]==0){
//將節點設置為已訪問
visit[t.node] = -1;
//將當前節點相連且未訪問的節點遍歷
for (int i = 0; i < n; i++) {
if (graph[t.node][i]!=0 && visit[i]==0) {
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){
return node1.cost-node2.cost;
}
}
- 參考資料
-
- 1. 劉小玲,李輝,郭治國.基於狄克斯特拉算法的車間動態生產能力評估與實現[J].微計算機信息,2006(12):96-98 ．CNKI．2006-04-30[引用日期2020-05-15]
- 2. 普里姆算法和迪克斯特拉算法的比較[J].計算機教育,2008(21):53-56 ．CNKI．2008-11-10[引用日期2020-05-15]
- 3. 高武,周公建,王陽.Dijkstra算法在臨時限速操作中的應用[J].電子世界,2020(08):31-32+35 ．CNKI．2020-04-30[引用日期2020-05-15]
- 4. 楊曉龍,曲東才.一種基於遺傳模擬退火算法的航跡優化方法[J].四川兵工學報,2013,34(12):66-70 ．CNKI．2013-12-25[引用日期2020-05-15]
