Single-Source Shortest Path:Dijkstra's Algorithm

Posted by Chiu CC on 3 07, 2016


先備知識與注意事項

本篇文章將介紹另一種處理Single-Source Shortest Path的方法:Dijkstra's Algorithm
演算法的概念依然需要:

  • Relaxation
  • Convergence property
  • Path-relaxation property

若有疑惑,傳送門在這裏

在演算法中,將會使用到Min-Priority Queue,包含三個基本操作(operation):

  • ExtractMin()
  • DecreaseKey()
  • MinHeapInsert(),不過本文以BuildMinHeap()取代;

若讀者需要稍作複習,請參考:


目錄


Dijkstra's Algorithm

若某一directed graph中,所有edge的weight皆為非負實數(\(weight\geq 0\)),如圖一(a),便能夠使用Dijkstra's Algorithm處理這個directed graph上的Single-Source Shortest Path問題。

cc

圖一(a)。

Dijkstra's Algorithm是一種「每次挑選當前最佳選擇(optimal solution)」的Greedy Algorithm

  1. 把vertex分成兩個集合,其中一個集合「S」中的vertex屬於「已經找到從起點vertex出發至該vertex的最短路徑」,另一個集合「Q」中的vertex則還沒有。
    • 非常重要:這裡的Q就是Min-Priority Queue,其中每一個HeapNodeelement即為「vertex的index」,key即為「vertex的distance」,表示從起點走到該vertex的path成本。
  2. 對所有vertex的predecessordistance進行初始化(見圖一(b)),並更新起點vertex之distance\(0\)
  3. 若Graph中有\(V\)個vertex,便執行\(V\)次迴圈。
  4. 在每一個迴圈的開始,從Q中挑選出「distance值最小」的vertex,表示已經找到「從起點vertex抵達該vertex之最短距離」,並將該vertex從Q中移除,放進S集合。
    • 利用ExtractMin()挑選「distance值最小」的vertex,即為Greedy Algorithm概念。
  5. 每一次迴圈都會藉由Relax()更新「從起點vertex到達仍屬於Q集合的vertex之path距離」,並將path距離存放於distance[]。並且利用DecreaseKey()更新Q中vertex的Key(也就是distance)。
    步驟四與步驟五為完整的一次迴圈。
  6. 進到下一個迴圈時,會繼續從Q中挑選出「distance最小」的vertex,放進S
  7. 重複上述步驟,直到Q中的vertex都被放進S為止。

如此便能得到從起點vertex抵達其餘vertex的最短路徑。

演算法將使用兩項資料項目predecessor[]distance[],其功能如下:

  • predecessor[]:記錄vertex是被哪個vertex所找到,由predecessor[]可以還原出Predecessor Subgraph,也就是Shortest-Path Tree
  • distance[]:記錄從起點vertex走到特定vertex的path之weight總和。


以下以圖一(a)之Graph為例,以vertex(0)為起點,進行Dijkstra's Algorithm

首先,對predecessor[]distance[]進行初始化:

  • 所有vertex的predecessor[]先設為\(-1\)
    • 若到演算法結束時,vertex(X)之predecessor[X]仍等於\(-1\),表示從起點vertex走不到vertex(X)。
  • 所有vertex的distance[]先設為「無限大(\(\infty\))」。
    • 若在演算法結束時,distance[]仍為「無限大(\(\infty\))」,表示,從起點vertex走不到vertex(X)。
  • 把起點vertex(0)之distance[0]設為\(0\),如此一來,當挑選Min-Priority Queue中,distance[]值最小的vertex,進行路徑探索時,就會從vertex(0)開始。

cc

圖一(b)。

接著便進入演算法的主要迴圈,包含兩個步驟:

  1. ExtractMin():從Min-Priority Queue,也就是Q中,選出distance最小的vertex,並將其從Q中移除。
  2. Relax()以及DecreaseKey():對選出的vertex所連結的edge進行Relax(),更新distancepredecessor,並同步更新Q

第一次迴圈:

Q中以ExtractMin(),取得目前distance值最小的vertex:起點vertex(0)。
建立一個變數int u記住vertex(0),並將vertex(0)從Q移除,表示已經找到從起點vertex走到vertex(0)的最短路徑,見圖二(a)。

cc

圖二(a)。

接著,以vertex(0)為探索起點,尋找所有「從vertex(0)指出去」的edge,進行:

  • Relax():以圖二(b)為例,從vertex(0)能夠走到vertex(1)、vertex(5),便利用Relax()更新從起點vertex,經過vertex(0)後抵達vertex(1)、vertex(5)的path之weight總和,存放進distance[],同時更新predecessor[]
    • vertex(1)能夠從vertex(0)以成本「\(8\)」走到,比原先的「無限大(\(\infty\))」成本要低,因此,更新:
      • distance[1]=distance[0]+weight(0,1)
      • predecessor[1]=0
    • 對vertex(5)比照辦理。
  • DecreaseKey():在更新distance[]之後,也要同步更新Q中HeapNode的資料。

cc

圖二(b)。


第二次迴圈:

繼續從Q中選出distance最小的vertex(5),並將vertex(5)從Q中移除,表示已經找到「從起點vertex(0)走到vertex(5)」的最短距離,如圖三(a)。

cc

圖三(a)。

關鍵是,為什麼從Q中挑選distance最小的vertex(X),就能肯定已經找到「從起點vertex走到vertex(X)之最短路徑」,distance[X]\(=\delta(0,X)\)

這裡不進行嚴謹證明(證明請參考:Ashley Montanaro:Priority queues and Dijkstra’s algorithm),只就基本條件推論。

前面提到,Dijkstra's Algorithm的使用時機是,當Graph中的weight皆為非負實數(\(weight\geq 0\)),此時:

  • Graph中的所有cycle之wieght總和必定是正值(positive value);
  • 亦即,路徑中的edge越多,其weight總和只會增加或持平,不可能減少。

那麼再看圖三(a),從vertex(0)走到vertex(5)有兩個選擇:

  1. 一個是經過edge(0,5),成本為\(1\)
  2. 另一個是經過edge(0,1),再經過其他vertex(例如,\(Path:0-1-2-3-5\)),最後抵達vertex(5),由於edge(0,1)之weight已經是\(8\),可以確定的是,經過edge(0,1)的這條path之weight總和必定大於\(8\)

顯然,直接經過edge(0,5)會是從vertex(0)走到vertex(5)最短的路徑。

更廣義地說,從Q中挑選distance最小之vertex,並將其從Q中移除,必定表示,已經找到從起點vertex走到該vertex之最短路徑。


接著,重複上述步驟:

  • Relax():對所有「從vertex(5)指出去」的edge進行Relaxation
  • DecreaseKey():同步更新Q中的vertex之distance[]

cc

圖三(b)。

接下來,第三次迴圈至第六次迴圈(直到Q中的vertex都被移除)的步驟如上述,見圖四(a)-圖七(a)。

第三次迴圈:

cc

圖四(a)。

cc

圖四(b)。

第四次迴圈:

cc

圖五(a)。

cc

圖五(b)。

第五次迴圈:

cc

圖六(a)。

cc

圖六(b)。

第六次迴圈:

cc

圖七(a)。

圖七(a)便是從vertex(0)走到Graph中其餘vertex之最短路徑Predecessor Subgraph


程式碼

程式碼包含幾個部分:

class BinaryHeapstruct HeapNode:以Binary Heap實現Min-Priority Queue,概念與範例程式碼請參考Priority Queue:Binary Heap

class Graph_SP

  • 基本的資料項目:AdjListnum_vertexpredecessordistance
  • Relax()InitializeSingleSource()之功能與Bellman-Ford Algorithm所使用相同。
  • Dijkstra():功能如前一小節所述。
  • class BinaryHeap設為class Graph_SP的「friend」,才能夠把distance[]放進Min Heap中。

以及main():建立如圖一(a)之AdjList,並進行Dijkstra()

// C++ code
#include <iostream>
#include <vector>
#include <list>
#include <utility>          // for std::pair<>
#include <iomanip>          // for std::setw()
#include <cmath>            // for std::floor
#include "Priority_Queue_BinaryHeap.h"

const int Max_Distance = 100;
class Graph_SP{             // SP serves as Shortest Path
private:
    int num_vertex;
    std::vector<std::list<std::pair<int,int>>> AdjList;
    std::vector<int> predecessor, distance;
    std::vector<bool> visited;
public:
    Graph_SP():num_vertex(0){};
    Graph_SP(int n):num_vertex(n){
        AdjList.resize(num_vertex);
    }
    void AddEdge(int from, int to, int weight);
    void PrintDataArray(std::vector<int> array);
    void PrintIntArray(int *array);

    void InitializeSingleSource(int Start);     // 以Start作為起點
    void Relax(int X, int Y, int weight);       // edge方向:from X to Y

    void Dijkstra(int Start = 0);        // 需要Min-Priority Queue
    friend class BinaryHeap;             // 以Binary Heap實現Min-Priority Queue
};
void Graph_SP::Dijkstra(int Start){

    InitializeSingleSource(Start);

    BinaryHeap minQueue(num_vertex);   // object of min queue
    minQueue.BuildMinHeap(distance);

    visited.resize(num_vertex, false);   // initializa visited[] as {0,0,0,...,0}

    while (!minQueue.IsHeapEmpty()) {
        int u = minQueue.ExtractMin();
        for (std::list<std::pair<int, int>>::iterator itr = AdjList[u].begin();
             itr != AdjList[u].end(); itr++) {

            Relax(u, (*itr).first, (*itr).second);
            minQueue.DecreaseKey((*itr).first, distance[(*itr).first]);
        }
    }
    std::cout << "\nprint predecessor:\n";
    PrintDataArray(predecessor);
    std::cout << "\nprint distance:\n";
    PrintDataArray(distance);
}
void Graph_SP::InitializeSingleSource(int Start){

    distance.resize(num_vertex);
    predecessor.resize(num_vertex);

    for (int i = 0; i < num_vertex; i++) {
        distance[i] = Max_Distance;
        predecessor[i] = -1;
    }
    distance[Start] = 0;
}
void Graph_SP::Relax(int from, int to, int weight){

    if (distance[to] > distance[from] + weight) {
        distance[to] = distance[from] + weight;
        predecessor[to] = from;
    }
}
void Graph_SP::AddEdge(int from, int to, int weight){

    AdjList[from].push_back(std::make_pair(to,weight));
}
void Graph_SP::PrintDataArray(std::vector<int> array){
    for (int i = 0; i < num_vertex; i++)
        std::cout << std::setw(4) << i;
    std::cout << std::endl;
    for (int i = 0; i < num_vertex; i++)
        std::cout << std::setw(4) << array[i];
    std::cout << std::endl;
}
int main(){

    Graph_SP g9(6);
    g9.AddEdge(0, 1, 8);g9.AddEdge(0, 5, 1);
    g9.AddEdge(1, 0, 3);g9.AddEdge(1, 2, 1);
    g9.AddEdge(2, 0, 5);g9.AddEdge(2, 3, 2);g9.AddEdge(2, 4, 2);
    g9.AddEdge(3, 1, 4);g9.AddEdge(3, 2, 6);g9.AddEdge(3, 4, 7);g9.AddEdge(3, 5, 3);
    g9.AddEdge(5, 3, 2);g9.AddEdge(5, 4, 8);

    g9.Dijkstra(0);

    return 0;
}

output:

new key is larger than current key
new key is larger than current key

print predecessor:
   0   1   2   3   4   5
  -1   3   1   5   5   0

print distance:
   0   1   2   3   4   5
   0   7   8   3   9   1

小小備註(可能不是很重要):

output中的「new key is larger than current key」來自於Min-Priority Queue中的DecreaseKey()
DecreaseKey()只允許將Min-Priority Queue中的node之Key「降低」,不能「增加」,所以當要求「增加」時,便中止該函式。

那麼以此例而言,什麼時候會出現「new key is larger than current key」呢?

就是當vertex(X)想要對vertex(Y)進行Relaxation卻失敗的時候,以此例而言:

  • 第一次發生在圖四(a)與圖四(b),要以vertex(3)對其他「還存在Min-Priority Queue中」而且「與vertex(3)相連」的vertex進行Relaxation時(在vertex(3)因為distance最小而被當作起點之前,vertex(0)與vertex(5)已經從Q中移除了,因此目前只剩下vertex(1)、vertex(2)、vertex(4)與之相連),因為vertex(4)當下的distance(從vertex(5)走到vertex(4)的成本)會比從vertex(3)走到vertex(4)還低(成本distance[3]+weight(3,4)\(3+7=10\)),所以在Relaxation後,distance[4]維持不變,那麼在minQueue進行DecreaseKey()時,就不會對vertex(4)的Key(也就是distance[4])進行調整。
  • 第二次發生在圖六(a)與圖六(b),以vertex(2)對vertex(4)進行Relaxation時,理由與第一次一樣:「從vertex(2)走到vertex(4)的成本」比「從vertex(5)走到vertex(4)的成本」還高,所以不更新distance[4]



最後,關於Dijkstra's Algorithm之時間複雜度,會因為Min-Priority Queue所使用的資料結構(例如,Binary Heap或是Fibonacci Heap)而有所差異,可能最差從\(O(V^2+E)\)到最好\(O(V\log V+E)\),請參考以下連結之討論:


以上便是Dijkstra's Algorithm之介紹。

讀者不妨嘗試比較Dijkstra's AlgorithmBellman-Ford Algorithm之差異,一般情況下,Dijkstra's Algorithm應該會較有效率,不過限制是Graph之weight必須是非負實數(nonnegative real number),若遇到weight為負數時,仍需使用Bellman-Ford Algorithm



參考資料:


Shortest Path系列文章

Shortest Path:Intro(簡介)
Single-Source Shortest Path:Bellman-Ford Algorithm
Single-Source Shortest Path:on DAG(directed acyclic graph)
Single-Source Shortest Path:Dijkstra's Algorithm
All-Pairs Shortest Path:Floyd-Warshall Algorithm

回到目錄:

目錄:演算法與資料結構