# [資料結構] CH18. Shortest Path Algorithms

## Topological Sorting
* 中文叫**拓撲排序**，是用於有向無環圖(directed acyclic graph,DAG)的一種線性排序。
* 如果DAG的點A指向點B，拓撲排序中點A一定要在點B前面。
* 一張DAG至少有一種拓撲排序，但可能有更多。
* 下圖的拓撲排序共有：
* ABCDE
* ABCED
* ACBED
* ACBDE

digraph topologicalSort
{
    A->B->E
    A->C->D
    B->D
    C->E
}

## Spanning Tree
* 一張graph的生成樹是該graph的subgraph，且該subgraph所有點都被連到且沒有circle的出現。
* 以下為範例，但該圖的Spanning Tree還有很多張。

graph span
{
    subgraph cluster1
    {
        label="原圖"
        A[label="A"]
        B[label="B"]
        C[label="C"]
        D[label="D"]
        A--B--C--A--D--C;
        B--D
        {rank="same";A;B}
        {rank="same";C;D}
    }
    subgraph cluster2
    {
        label="Spanning Tree 1"
        A2[label="A"]
        B2[label="B"]
        C2[label="C"]
        D2[label="D"]
        A2--B2--C2--D2;
        {rank="same";A2;B2}
        {rank="same";C2;D2}
    }
    subgraph cluster3
    {
        label="Spanning Tree 2"
        A3[label="A"]
        B3[label="B"]
        C3[label="C"]
        D3[label="D"]
        A3--B3--C3
        B3--D3
        {rank="same";A3;B3}
        {rank="same";C3;D3}
    }
}

## Minimum Spanning Tree
* 在討論最小生成樹之前，我們要先把權重加上去，沒有權重就不知道怎麼比大小了。

graph span
{
    subgraph cluster1
    {
        label="原圖(加權重)"
        A[label="A"]
        B[label="B"]
        C[label="C"]
        D[label="D"]
        A--B[label="1"]
        B--C[label="2"]
        C--A[label="3"]
        A--D[label="4"]
        D--C[label="5"]
        B--D[label="6"]
        {rank="same";A;B}
        {rank="same";C;D}
    }
}

* 最小生成樹就是所有權重相加之後，總和最小的圖。
* 以上圖為例子，該圖的最小生成樹就是：

graph span
{
    subgraph cluster1
    {
        label="最小生成樹"
        A[label="A"]
        B[label="B"]
        C[label="C"]
        D[label="D"]
        A--B[label="1"]
        B--C[label="2"]
        A--D[label="4"]
        {rank="same";A;B}
        {rank="same";C;D}
    }
}

## Shortest Path Algorithms
* 現在問題來了，我們要如何從一張圖找出它的最小生成樹？
* 一共有三種演算法可以幫我們找最短路徑
* Prim’s algorithm
* Kruskal’s algorithm
* Dijkstra’s algorithm
* 其中前面兩個可以找到最小生成樹，而Dijkstra’s algorithm則是可以找出任意節點到其他所有點的最短距離。

### Prim’s algorithm
* 條件：給予所有edge的兩點與權重，和一個起始點。
* 做法：從起始點開始，在與其相連且尚未被選取的節點裡，選擇權重最小的邊，將新的節點加入。重複至所有點都被加入。
* 範例：使用Prim’s algorithm，以A為起始點找出MST。

graph prim
{
    A--B[label="7"]
    A--C[label="3"]
    B--E[label="11"]
    C--D[label="10"]
    C--B[label="4"]
    D--B[label="9"]
    {rank="same";A;B;E}
    {rank="same";C;D}
}

* 將點A加入，目前探索到的邊為AB和AC。

graph prim
{
    A[color="red"]
    A--B[label="7",color="red"]
    A--C[label="3",color="red"]
    B--E[label="11"]
    C--D[label="10"]
    C--B[label="4"]
    D--B[label="9"]
    {rank="same";A;B;E}
    {rank="same";C;D}
}

* 因為AC權重最小，將點C加入。點C加入後又多了BC和CD兩條邊。

graph prim
{
    A[color="red"]
    C[color="red"]
    A--B[label="7",color="red"]
    A--C[label="3",color="blue"]
    B--E[label="11"]
    C--D[label="10",color="red"]
    C--B[label="4",color="red"]
    D--B[label="9"]
    {rank="same";A;B;E}
    {rank="same";C;D}
}

* BC權重最小，加入點B。多了BD和BE兩條邊。

graph prim
{
    A[color="red"]
    B[color="red"]
    C[color="red"]
    A--B[label="7",color="red"]
    A--C[label="3",color="blue"]
    B--E[label="11",color="red"]
    C--D[label="10",color="red"]
    C--B[label="4",color="blue"]
    D--B[label="9",color="red"]
    {rank="same";A;B;E}
    {rank="same";C;D}
}

* AB權重最小，但AB兩點都已經加入，若選擇AB會形成circle，所以將AB捨棄。

graph prim
{
    A[color="red"]
    B[color="red"]
    C[color="red"]
    A--B[label="7",color="red",style="dashed"]
    A--C[label="3",color="blue"]
    B--E[label="11",color="red"]
    C--D[label="10",color="red"]
    C--B[label="4",color="blue"]
    D--B[label="9",color="red"]
    {rank="same";A;B;E}
    {rank="same";C;D}
}

* 接下來是BD權重最小。

graph prim
{
    A[color="red"]
    B[color="red"]
    C[color="red"]
    D[color="red"]
    A--B[label="7",color="red",style="dashed"]
    A--C[label="3",color="blue"]
    B--E[label="11",color="red"]
    C--D[label="10",color="red"]
    C--B[label="4",color="blue"]
    D--B[label="9",color="blue"]
    {rank="same";A;B;E}
    {rank="same";C;D}
}

* CD也都加入過了，捨棄。

graph prim
{
    A[color="red"]
    B[color="red"]
    C[color="red"]
    D[color="red"]
    A--B[label="7",color="red",style="dashed"]
    A--C[label="3",color="blue"]
    B--E[label="11",color="red"]
    C--D[label="10",color="red",style="dashed"]
    C--B[label="4",color="blue"]
    D--B[label="9",color="blue"]
    {rank="same";A;B;E}
    {rank="same";C;D}
}

* 最後是BE。

graph prim
{
    A[color="red"]
    B[color="red"]
    C[color="red"]
    D[color="red"]
    E[color="red"]
    A--B[label="7",color="red",style="dashed"]
    A--C[label="3",color="blue"]
    B--E[label="11",color="blue"]
    C--D[label="10",color="red",style="dashed"]
    C--B[label="4",color="blue"]
    D--B[label="9",color="blue"]
    {rank="same";A;B;E}
    {rank="same";C;D}
}

* 因此這張圖的MST為AC、BC、BD和BE。

### Kruskal’s algorithm
* 條件：給予所有edge的兩點與權重，**不需要**起始點。
* 做法：一開始所有的點都是獨立的樹。不停地將最小的邊所相連的兩個點合併成同一個樹(如果本來就是同一個樹就不能選擇那條邊)，直到所有邊都跑過一輪。
* 範例：使用Kruskal’s algorithm找出MST。

graph kruskal
{
    A[color="red"]
    B[color="blue"]
    C[color="orange"]
    D[color="purple"]
    E[color="gray"]
    A--B[label="3"]
    B--C[label="5"]
    C--D[label="2"]
    D--E[label="7"]
    A--E[label="1"]
    E--B[label="4"]
    E--C[label="6"]
    {rank="same";A;E}
    {rank="same";B;C;D}
}

* 最小的邊是AE，將AE合併至同一個樹。

graph kruskal
{
    A[color="red"]
    B[color="blue"]
    C[color="orange"]
    D[color="purple"]
    E[color="red"]
    A--B[label="3"]
    B--C[label="5"]
    C--D[label="2"]
    D--E[label="7"]
    A--E[label="1",color="red"]
    E--B[label="4"]
    E--C[label="6"]
    {rank="same";A;E}
    {rank="same";B;C;D}
}

* 接下來是CD。

graph kruskal
{
    A[color="red"]
    B[color="blue"]
    C[color="purple"]
    D[color="purple"]
    E[color="red"]
    A--B[label="3"]
    B--C[label="5"]
    C--D[label="2",color="red"]
    D--E[label="7"]
    A--E[label="1",color="red"]
    E--B[label="4"]
    E--C[label="6"]
    {rank="same";A;E}
    {rank="same";B;C;D}
}

* 然後是AB。

graph kruskal
{
    A[color="red"]
    B[color="red"]
    C[color="purple"]
    D[color="purple"]
    E[color="red"]
    A--B[label="3",color="red"]
    B--C[label="5"]
    C--D[label="2",color="red"]
    D--E[label="7"]
    A--E[label="1",color="red"]
    E--B[label="4"]
    E--C[label="6"]
    {rank="same";A;E}
    {rank="same";B;C;D}
}

* BE已經在同一個樹了，所以不能使用這條邊合併。

graph kruskal
{
    A[color="red"]
    B[color="red"]
    C[color="purple"]
    D[color="purple"]
    E[color="red"]
    A--B[label="3",color="red"]
    B--C[label="5"]
    C--D[label="2",color="red"]
    D--E[label="7"]
    A--E[label="1",color="red"]
    E--B[label="4",style="dashed"]
    E--C[label="6"]
    {rank="same";A;E}
    {rank="same";B;C;D}
}

* BC合併所有點了。

graph kruskal
{
    A[color="red"]
    B[color="red"]
    C[color="red"]
    D[color="red"]
    E[color="red"]
    A--B[label="3",color="red"]
    B--C[label="5",color="red"]
    C--D[label="2",color="red"]
    D--E[label="7"]
    A--E[label="1",color="red"]
    E--B[label="4",style="dashed"]
    E--C[label="6"]
    {rank="same";A;E}
    {rank="same";B;C;D}
}

* 所有點都已經相連，因此MST是AE、AB、BC、CD。

### Dijkstra’s algorithm
* 條件：給予所有edge的兩點與權重(有向)，和一個起始點。
* 做法：使用BFS的概念，不停搜索和更新起始點到所有點的最短距離。
* 範例：Dijkstra’s algorithm，以D為起始點找出到所有點的最短距離。

digraph dijkstra
{
    B->A[label="4"]
    A->C[label="2"]
    D->B[label="15"]
    D->F[label="5"]
    D->G[label="23"]
    F->C[label="9"]
    F->G[label="13"]
    E->G[label="11"]
    E->B[label="17"]
    {rank="same";A;B}
    {rank="same";C;D;E}
    {rank="sink";F;G}
}

* 從點D開始，因此已知最近距離是DB、DG、DF，其中最小的是DF，因此F設為已知最小值。

digraph dijkstra
{
    
    B->A[label="4"]
    A->C[label="2"]
    D->B[label="15",color="blue"]
    D->F[label="5",color="red"]
    D->G[label="23",color="blue"]
    F->C[label="9",color="blue"]
    F->G[label="13",color="blue"]
    E->G[label="11"]
    E->B[label="17"]
    D[label="D 0"color="red"]
    F[label="F 5"color="red"]
    {rank="same";A;B}
    {rank="same";C;D;E}
    {rank="sink";F;G}
}

* 這時要注意，FC的權重不是`9`，還要考慮點F本身是`5`，因此FC的權重是`14`。
* 同理，FG是`18`。
* 一樣挑選最小的權重點，將點C設為已知最小值。

digraph dijkstra
{
    
    B->A[label="4"]
    A->C[label="2"]
    D->B[label="15",color="blue"]
    D->F[label="5",color="red"]
    D->G[label="23",color="blue"]
    F->C[label="9",color="red"]
    F->G[label="13",color="blue"]
    E->G[label="11"]
    E->B[label="17"]
    C[label="C 14"color="red"]
    D[label="D 0"color="red"]
    F[label="F 5"color="red"]
    {rank="same";A;B}
    {rank="same";C;D;E}
    {rank="sink";F;G}
}

* 接下來是點B。

digraph dijkstra
{
    B->A[label="4",color="blue"]
    A->C[label="2"]
    D->B[label="15",color="red"]
    D->F[label="5",color="red"]
    D->G[label="23",color="blue"]
    F->C[label="9",color="red"]
    F->G[label="13",color="blue"]
    E->G[label="11"]
    E->B[label="17"]
    B[label="B 15"color="red"]
    C[label="C 14"color="red"]
    D[label="D 0"color="red"]
    F[label="F 5"color="red"]
    {rank="same";A;B}
    {rank="same";C;D;E}
    {rank="sink";F;G}
}

* 接下來是點G。

digraph dijkstra
{
    B->A[label="4",color="blue"]
    A->C[label="2"]
    D->B[label="15",color="red"]
    D->F[label="5",color="red"]
    D->G[label="23",color="blue"]
    F->C[label="9",color="red"]
    F->G[label="13",color="red"]
    E->G[label="11"]
    E->B[label="17"]
    B[label="B 15"color="red"]
    C[label="C 14"color="red"]
    D[label="D 0"color="red"]
    F[label="F 5"color="red"]
    G[label="G 18"color="red"]
    {rank="same";A;B}
    {rank="same";C;D;E}
    {rank="sink";F;G}
}

* 然後是點A。

digraph dijkstra
{
    B->A[label="4",color="red"]
    A->C[label="2",color="blue"]
    D->B[label="15",color="red"]
    D->F[label="5",color="red"]
    D->G[label="23",color="blue"]
    F->C[label="9",color="red"]
    F->G[label="13",color="red"]
    E->G[label="11"]
    E->B[label="17"]
    A[label="A 19"color="red"]
    B[label="B 15"color="red"]
    C[label="C 14"color="red"]
    D[label="D 0"color="red"]
    F[label="F 5"color="red"]
    G[label="G 18"color="red"]
    {rank="same";A;B}
    {rank="same";C;D;E}
    {rank="sink";F;G}
}

* 剩下的邊AC和DG都用不到，而EB和EG是無法使用。
* 因此從點D到所有點的最小距離就出來了：
* A: 19
* B: 15
* C: 14
* D: 0(自己本身)
* E: 無法到達
* F: 5
* G: 18

### Prim和Kruskal的差異
* Prim和Kruskal都是求出MST的演算法，其中最大的差別在於：

###### tags: `DS` `note`