## :speech_balloon: 介紹
Dijkstra 演算法的目的為找出G(V, E)圖上某一點到另一點的最短路徑，是一種Greedy Algorithm，搭配Binary Heap來尋找最短路徑所需的時間是O(E log(V))。在現實生活中，它則是應用在網路、地圖、交通...。

:::info
G = Graph、 V = Verices (節點)、 E = Edges(邊)
:::

:::warning
本篇文章從基礎到進階實作皆有，下面是關於建議閱讀章節

* 初學者
* 觀念
* 中階者
* 觀念
* Code Segments (基礎)

**參考章節**：Code Segments using STL and min-heap (進階)
:::
* 先備知識
* 基本圖論
* 基本資料結構
* C++ program

* 文章分類 (參考)
* 難度：★★★
* 重要程度：★★

## :book: 觀念
---
:::warning
:bulb: 如果看不太懂虛擬碼可以看演算法解析，先跳過再回來理解虛擬碼
:::

### ==1. Pseudocode==
### `Dijkstra's algorithm to generate single-source shortest path`

**Input：** A directed graph $G=(V,E)$ and a source vertex $v_0$.
For each edge $(u,v)\in E$ ,there is a non-negative number $c(u,v)$ associated with it.$|V|=n+1$
<span style="color:green">//輸入為一有向圖 $G=(V,E)$ 以及起始點 $v_0$，對於任意邊 $E$ 皆有一個非負整數 $c$ 關聯(距離)，而點的個數有$n+1$個 ( 編號從$0$到$n$ ) </span>

**Output：** For each $v\in V$ ,the length of a shortest path from $v_0$ to
<span style="color:green">//輸出為起始點$v_0$至任意點$v$之最短路徑長</span>

**Pseudocode：**
\begin{align}
&\color{blue}{\{initial\}}\\\\
&S:=\{v_0\} {\small \color{green}{\;//一開始把v_0加入到S已走訪集合}}\\\\
&For\;i:=1\;to\;n\;do\\\\
&Begin\\\\
&{\small \color{green}{\;//如果v_0與v_i有邊，則將此邊距離暫時作為到v_i所花費的距離，若沒有則代表距離無限}}\\\\
&\;\;\;if\;(v_0,v_i)\in E\;then\\\\
&\;\;\;\;\;\;\;\;\;\;L(v_i):=c(v_0,v_i)\\\\
&\;\;\;else\\\\
&\;\;\;\;\;\;\;\;\;\;L(v_i):=\infty\\\\
&End\\\\
& \color{blue}{\{renew\;distance\;untill\;find\;the\;shortest\;distance\}}\\\\
&For\;i:=1\;to\;n\;do\\\\
&Begin\\\\
&{\small \color{green}{\;//從還未被挑選過的Vertex集合，挑選u點使得到u點的距離最短}}\\\\
&\;\;\;Choose\;u\;from\;V-S\;such\;that\;L(u)\;is\;the\;smallest\\\\
&\;\;\;S:=S\;\cup\;\{u\}\;(^*\;Put\;u\;into\;S^*)\\\\
&{\small \color{green}{\;//更新目前的L(距離表)，如果以u點作為中繼站是否有更短的距離?如果是則更新L\;}}\\\\
&\;\;\;For\;all\;w\;in\;V-S\;do\\\\
&\;\;\;\;\;\;\;\;\;\;L(w):=min(L(w),L(u)+c(u,w))\\\\
&End\\\\
\end{align}
### ==2. 演算法解析==
### **Step1. 從v~0~出發與初始化L(距離表)**
$S=\{v_0\}$
$V-S=\{v_1,v_2,v_3,v_4,v_5\}$
| v~1~ | v~2~ | v~3~ | v~4~ | v~5~ |
| ---- | ---- | ---- | ---- | ---- |
| <span style="color:red">1</span> | 6 | ∞ | ∞ | ∞ |
### **Step2. Choose v~1~ 開始更新各點距離**
$S=\{v_0,v_1\}$
$V-S=\{v_2,v_3,v_4,v_5\}$
挑選最短距離邊，故選擇$v_1$為$u$，透過$v_1$到各點距離更新距離表，剩下回合依此類推
| Pass | v~1~ | v~2~ | v~3~ | v~4~ | v~5~ |
| --- | ---- | ---- | ---- | ---- | ---- |
| **1** | 1 | 6 | ∞ | ∞ | ∞ |
| **2** | - | <span style="color:red">4</span> | 5 | 7 | ∞ |
### **Step3. Choose v~2~更新各點距離**
$S=\{v_0,v_1,v_2\}$
$V-S=\{v_3,v_4,v_5\}$
| Pass | v~1~ | v~2~ | v~3~ | v~4~ | v~5~ |
| ----- | ---- | -------------------------------- | ---- | ---- | ---- |
| **1** | 1 | 6 | ∞ | ∞ | ∞ |
| **2** | - | 4 | 5 | 7 | ∞ |
| **3** | - | - | <span style="color:red">5</span> | 6 | ∞ |
### **Step4. Choose v~3~更新各點距離**
$S=\{v_0,v_1,v_2,v_3\}$
$V-S=\{v_4,v_5\}$
| Pass | v~1~ | v~2~ | v~3~ | v~4~ | v~5~ |
| ----- | ---- | -------------------------------- | ---- | ---- | ---- |
| **1** | 1 | 6 | ∞ | ∞ | ∞ |
| **2** | - | 4 | 5 | 7 | ∞ |
| **3** | - | - | 5 | 6 | ∞ |
| **4** | - | - | - | <span style="color:red">6</span> | 8 |
### **Step5. Choose v~4~更新各點距離**
$S=\{v_0,v_1,v_2,v_3,v_4\}$
$V-S=\{v_5\}$
| Pass | v~1~ | v~2~ | v~3~ | v~4~ | v~5~ |
| ----- | ---- | -------------------------------- | ---- | ---- | ---- |
| **1** | 1 | 6 | ∞ | ∞ | ∞ |
| **2** | - | 4 | 5 | 7 | ∞ |
| **3** | - | - | 5 | 6 | ∞ |
| **4** | - | - | - | 6 | 8 |
| **5** | - | - | - | - | <span style="color:red">8</span> |
### **Step5. Choose v~5~結束**
$S=\{v_0,v_1,v_2,v_3,v_4,v_5\}$
$V-S=\{\}$
| Pass | v~1~ | v~2~ | v~3~ | v~4~ | v~5~ |
| ----- | ---- | -------------------------------- | ---- | ---- | ---- |
| **1** | 1 | 6 | ∞ | ∞ | ∞ |
| **2** | - | 4 | 5 | 7 | ∞ |
| **3** | - | - | 5 | 6 | ∞ |
| **4** | - | - | - | 6 | 8 |
| **5** | - | - | - | - | 8|
| **6** | - | - | - | - | - |
### **Step6. 總結**
:::success
### Ans：若從$v_0$出發至各點的最短距離為
| v~1~ | v~2~ | v~3~ | v~4~ | v~5~ |
| ---- | ---- | ---- | ---- | ---- |
| 1 | 4 | 5 | 6 | 8 |
:::

## :book: Code Segments(基礎)
---

#include <iostream>
#define INF 0x3f3f3f3f
#define V_COUNT 6
using namespace std;

int adj[V_COUNT][V_COUNT];

void print_answer(int* L){
    printf("Vertex Distance from Source\n");
    for(int i = 0 ; i < V_COUNT; i++){
        printf("%d \t\t %d\n",i,L[i]);
    }
}
//初始化相鄰陣列(Adjacency Array)都是沒有邊的情況
void init_adj(){
    for(int i = 0 ; i < V_COUNT; i++){
        for(int j = 0 ; j < V_COUNT; j++){
            adj[i][j]=INF;
        }
    }
}

//加入邊與權重(距離)
void addEdge(int u,int v,int w){
    adj[u][v] = w;
    adj[v][u] = w;
}

//初始化圖
void init_graph(){
    init_adj();

    addEdge(0, 1, 1);
    addEdge(0, 2, 6);
    addEdge(1, 2, 3);
    addEdge(1, 3, 4);
    addEdge(1, 4, 6);
    addEdge(2, 3, 2);
    addEdge(2, 4, 2);
    addEdge(3, 5, 3);
    addEdge(3, 4, 2);
    addEdge(4, 5, 4);
}

void initial(int* L_table,int* S){

    //初始化 S集合
    for(int i=0; i < V_COUNT;i++){
        S[i]=0;
    }
    //將v0放入S集合
    S[0] = 1;

    //初始化L
    for(int i = 0 ; i < V_COUNT;i++){
        L_table[i]=INF;
    }
    L_table[0]=0;

    //如果v_0與v_i有邊，則將此邊距離暫時作為到v_i所花費的距離，若沒有則代表距離無限
    for(int i=1; i < V_COUNT;i++){
        if(adj[0][i]!=INF){
            L_table[i]=adj[0][i];
        }
        else{
            L_table[i]=INF;
        }
    }
}


int choss_u_smallest(int* S,int* L_table){
    int min = INF;
    int flag=0;
    int vertex;
    //找最小距離
    for(int i = 1 ; i < V_COUNT; i++){
        if(S[i]==0 && L_table[i]<min){
            flag=1;
            min = L_table[i];
            vertex = i;
        }
    }
    if(flag){
        //將挑選的vertex加入到集合s
        S[vertex]=1;
        //回傳vertex
        return vertex;
    }
    else{
        //V-S集合為空
        return -1;
    }
}
void renew_distance(int* L,int* S){
    int vertex;
    while(true){
        vertex=choss_u_smallest(S,L);

        if(vertex==-1)break;

        //更新L表
        for(int i = 1 ; i < V_COUNT;i++){
            if(i != vertex){
                int new_distance = L[vertex]+adj[vertex][i];
                if(L[i] > new_distance)L[i]=new_distance;
            }
        }

    }
}

int main()
{
    int S_set[V_COUNT];
    int L_table[V_COUNT];
    init_graph();
    initial(L_table,S_set);
    renew_distance(L_table,S_set);
    print_answer(L_table);
    return 0;
}

## :book: Code Segments using STL and min-heap (進階)
---

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f

typedef pair<int,int> iPair;

//類別
class Graph{
    int V; //有多少個點(Vertices)

    list<pair<int,int>>* adj; //用相鄰串列(Adjacency List)記錄圖(Graph)

public:
    Graph(int V);//建構子

    //添加E(邊)與權重，其中E(邊)是由兩個點(vertices)構成
    void addEdge(int u,int v,int w);

    //印出最短路徑
    void shortestPath(int s);
};

//類別實作

Graph::Graph(int V){
    this->V = V;//有多少個點(Vertices)
    adj = new list<iPair>[V];//創建相鄰串列(Adjacency List)，有V個點就有V個串列
}

void Graph::addEdge(int u,int v,int w){
    adj[u].push_back(make_pair(v,w));//以u為主的list儲存點v與到點v的權重(w)
    adj[v].push_back(make_pair(u,w));//v也可以到u
}

//印出點src到所有點的距離
void Graph::shortestPath(int src){

    //創建priority queue用於儲存vertices與距離，快速決定該回合最小距離
    //對於priority_queue的用法可以查看下面連結教學
    // https://www.geeksforgeeks.org/implement-min-heap-using-stl/
    priority_queue<iPair, vector<iPair>,greater<iPair>> pq;

    //設定到所有點的距離為無限(INF)
    //vector可以想成進階版array，下面的宣告代表
    //dist[0]=INF,dist[1]=INF,...,dist[V-1]=INF
    vector<int> dist(V, INF);

    //將起始點放入priority queue並初始化
    //make_pair(distance,vertex)
    //將起始點設定為距離0
    pq.push(make_pair(0,src));
    dist[src]=0;

    //持續loop直到priority queue為空
    while(!pq.empty()){

        //第一個vertex一定是起始點且他距離是0
        //pair的內容是(distance,vertex)
        //pair的第一項內容是距離(distance or weight)
        //pair的第二項內容是點(vertex)

        int u = pq.top().second;//取出vertex
        pq.pop();//取出後從pq移除

        //利用迭代器去走訪list
        list<pair<int,int>>::iterator i;
        //走訪當前vertex u的相鄰串列(走訪目前u能到的點)
        for(i = adj[u].begin();i!=adj[u].end();++i){

            int v = (*i).first;//u能到v點
            int weight = (*i).second;//u到v點的距離

            //如果從(起始點 ->u -> v)的距離小於目前所記錄 (起始點-> v) 的距離
            //代表找到更短的路徑，更新目前到該點最短距離
            //並將(distance,vertex)加入priority queue，等到迴圈結束再來評估下一步要前往哪個vertex(挑最小距離走)
            if(dist[v] > dist[u]+weight){
                dist[v] = dist[u]+weight;
                pq.push(make_pair(dist[v],v));
            }
        }

    }

    //迴圈結束後代表已經記錄完所有點的距離
    //印出
     printf("Vertex Distance from Source\n");
    for(int i = 0; i < V; ++i){
        printf("%d \t\t %d\n",i,dist[i]);
    }
}
int main()
{
    int V = 6;//有6個點
    Graph g(V);//創建圖

    //為點加上邊
    g.addEdge(0, 1, 1);
    g.addEdge(0, 2, 6);
    g.addEdge(1, 2, 3);
    g.addEdge(1, 3, 4);
    g.addEdge(1, 4, 6);
    g.addEdge(2, 3, 2);
    g.addEdge(2, 4, 2);
    g.addEdge(3, 5, 3);
    g.addEdge(3, 4, 2);
    g.addEdge(4, 5, 4);
    //從0開始走訪並印出
    g.shortestPath(0);

    return 0;
}


## :link: 參考
---
* [How to find Shortest Paths from Source to all Vertices using Dijkstra’s Algorithm](https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/)
* Introduction to the Design and Analysis of Algorithms (A Strategic Approach) R.C.T. Lee, S.S. Tseng, R.C. Chang, and Y.T. Tsai

###### tags: `資料結構` `Algorithm`