迪克斯特拉算法

迪傑斯特拉算法(Dijkstra)是由荷蘭計算機科學家狄克斯特拉於1959 年提出的，因此又叫狄克斯特拉算法。是從一個頂點到其餘各頂點的最短路徑算法，解決的是有權圖中最短路徑問題。迪傑斯特拉算法主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。

基本介紹

• 中文名：迪克斯特拉算法
• 外文名：Dijkstra's Algorithm
• 分類：計算機算法
• 用途：單源最短路徑問題

定義

Dijkstra算法一般的表述通常有兩種方式，一種用永久和臨時標號方式，一種是用OPEN, CLOSE表的方式，這裡均採用永久和臨時標號的方式。注意該算法要求圖中不存在負權邊。

原理

1.首先，引入一個輔助數組(vector)D，它的每個元素D 表示當前所找到的從起始點 （即源點 ）到其它每個頂點 的長度。

Dijkstra算法運行動畫過程

例如，D[3] = 2表示從起始點到頂點3的路徑相對最小長度為2。這裡強調相對就是說在算法執行過程中D的值是在不斷逼近最終結果但在過程中不一定就等於長度。

2.D的初始狀態為：若從 到 有弧（即從 到 存在連線邊），則D 為弧上的權值（即為從 到 的邊的權值）；否則置D 為∞。

顯然，長度為 D = Min{ D | ∈V } 的路徑就是從 出發到頂點 的長度最短的一條路徑，此路徑為( )。

3.那么，下一條長度次短的是哪一條呢？也就是找到從源點 到下一個頂點的最短路徑長度所對應的頂點，且這條最短路徑長度僅次於從源點 到頂點 的最短路徑長度。

假設該次短路徑的終點是 ，則可想而知，這條路徑要么是( )，或者是( )。它的長度或者是從 到 的弧上的權值，或者是D 加上從 到 的弧上的權值。

4.一般情況下，假設S為已求得的從源點 出發的最短路徑長度的頂點的集合，則可證明：下一條次最短路徑（設其終點為 ）要么是弧( )，或者是從源點 出發的中間只經過S中的頂點而最後到達頂點 的路徑。

因此，下一條長度次短的的最短路徑長度必是D = Min{ D | ∈V-S }，其中D 要么是弧( )上的權值，要么是D ( ∈S)和弧( , )上的權值之和。

算法描述如下：

1）令arcs表示弧上的權值。若弧不存在，則置arcs為∞（在本程式中為MAXCOST）。S為已找到的從 出發的的終點的集合，初始狀態為空集。那么，從 出發到圖上其餘各頂點 可能達到的長度的初值為D=arcs[Locate Vex(G, )]， ∈V；

2）選擇 ，使得D =Min{ D | ∈V-S } ；

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中頂點對應的距離值

若存在<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;    }}