昨天介紹了無向圖的最小生成樹來獲得無向圖中最短連通路徑的方式，今天要來討論有向圖的例子，如何在有向圖中給定一個起點，算出起點與其他點的最短距離。
雖然昨天沒特別提到有權無權，但昨天的兩個方式套在無權上都一樣是可以使用的，可以想見，有權的處理會比無權複雜(多考慮權重)。
今天我們會從無權有向圖開始探討，再進展到有權有向圖，在有權有向圖中被介紹的算法就會是 Dijkstra 算法。

無權有向圖

無權有向圖中，每條邊皆有向，權重相等，視為 1。
在一個無權有向圖中，要去辨別最小路徑，其實會長得很像 BFS。
我們會用一個陣列 Visited 紀錄全部的點，以下圖為例，visited = new bool[7]，陣列長度是節點個數。

 0 -> 1 -> 2 -> 5
 |    |         |
 v    v         v
 3 -> 4   ->    6

假設起點為 0，此時我們從將 visiste[0] 標為 true 表示已訪問，並把他相連的路徑都放入一個 queue 中，是從這個點可能出發的路徑、需要逐一檢查路徑需不需要。
接著迴圈檢查 queue 中，出來的點會 1,3，因為這兩個點都還沒被拜訪過，把 visited[1], visited[3] 都設為 true，接著把和 1 相連的 2,4，和 3 相連的 4 放入 queue 中待處理。
標 visited[2], visited[4] 為 true，把 5,6 放入 queue 中待處理，此時處理到剛剛由 3 延伸過來的 4，但因為 4 已經被拜訪過，所以我們可以忽略它，我們不再需要到這點的路徑了。
又因為我們是等步前進，類似 BFS 的概念，先到的必定步數和後到的相等或更少，以這裡為例，0-1-4 為 2 單位，0-3-4也為 2 單位，所以我們選用 0-1-4 即可，這裡的忽略是這樣來的。
目前在 queue 中的是 5,6，都未拜訪過，因此把 5,6 都標示為拜訪過，取用這兩條邊，而 5->6 的這條邊併不用再把 6 放入待處理的 queue，因為 6 以拜訪過，透過 0-1-4-6 這條 3 單位的路徑，再次印證無權中透過此方式遍歷已經到過的點必定等於或小於新的所需步數(0-1-2-5-6，4 單位)。

如果每次迴圈我們有對距離作累加，我們就能知道最後到各點的路徑各為多少、也能夠回答無權有向圖中必須要走訪所有節點及最短路徑的邊。
依上面的邏輯，最後出來的圖會長這樣。

 0 -> 1 -> 2 -> 5
 |    |         
 v    v         
 3    4   ->    6

這就是有向無權圖的實際算法逐步的展示。

有權有向圖

上面例子詳細展示了無權的例子，是因為有權的例子其實和無權幾乎一樣，只差在一件事：把 queue 變成 priority queue。
透過維護需遍歷路徑的大小，我們能保證優先確認權重小的路徑是否需要，如此來選出在有權有向圖中的最小權重路徑。

Network Delay Time

題目給予數條路徑，每條路徑 [i, j, w] 代表從點 i -> 點 j 權重為 w。
找出指定的起點 k 到其他全部點的所需花的最短時間中最長的時間，總共有 n 個點，若從起點 k 開始不能到其他全部點，則回傳 -1。

讓我列出邏輯步驟，可以嘗試跟著步驟寫寫看，或是用步驟對我的程式碼看各部分的實作怎麼操作。

1. 這種沒有提供好查詢結構的路徑，都建議自己拆成其他格式，相鄰矩陣就是其中一種通用的方式，所以根據 times 做出相鄰矩陣，相鄰矩陣初始值為正無窮(Int Max)，表示到不了，透過 times 更新
2. 初始化一個陣列，定義為從點 k 到下標索引 i 的最短距離，初始點 k 到自己為 0，到其他點為正無窮
3. 做一個變數用儲存答案，變數更新的時機是每次我們存數值第 2 步驟的陣列裡時，儲存比較大的選取路徑
4. 初始化一個優先級佇列，將點 k 相鄰的路徑通過相鄰矩陣放入，優先級對列的主儲存為點的索引 i(編號)，優先級為從點 k 到點 i 的距離，越近的越先處理
5. 開始循環，循環終止條件為優先級隊列為空的時候
6. 每次 Pop 出一個組合(i, k 到 i 的距離)時，比較目前 k 到 i 的距離是否已經比 Pop 出的還短，如果是，則跳過，如果 Pop 出的是比較短的，繼續迴圈
7. 更新 k 到 i 的距離，因為這條路徑讓 k 到 i 有更短路徑，也比較已儲存的 maxPath，確認是否當前儲存的路徑更大
8. 將 i 到其他點的路徑存入優先級對列，一樣是(點, k 到點的距離)這樣的組合，k 到點的距離為目前 k 到 i 的距離加上 i 到點的距離(這個從相鄰矩陣拿)，存入時也要判斷是否存入的路徑會比目前已存在的 k 到該點的距離更短，如果沒有，就不用存入了
9. 最後回傳的時候判斷是否 k 到其他點都有非正無窮的距離(初始值)，有距離表示能夠到，任一個為正無窮則回傳 -1，否則回傳第 3 步驟變數不斷更新後的最終答案

程式碼如下

public class Solution {
    public int NetworkDelayTime(int[][] times, int n, int k) {
        //adj[i][j] means node i to node j distance
        var adj = new int[n + 1][];
        for(var i = 0; i <= n; i++){
            adj[i] = new int[n + 1];
            Array.Fill(adj[i], Int32.MaxValue);
        }
        for(var i = 0; i < times.Length; i++){
            adj[times[i][0]][times[i][1]] = times[i][2];
        }
        //init the arr for start point k to other point's distance array
        //k to k is 0, k to other is unlimited in the initial
        var fromKToPath = new int[n + 1];
        Array.Fill(fromKToPath, Int32.MaxValue);
        fromKToPath[k] = 0;

        //For record the answer, update when each time new value save into fromKToPath
        var maxPath = 0;
        
        //PQ to decide which path should be proceed at first
        //More close to K, process at first
        var queue = new PriorityQueue<int, int>();
        for(var i = 0; i < adj[k].Length; i++){
            if(adj[k][i] != Int32.MaxValue){
                queue.Enqueue(i, adj[k][i]);
            }
        }
        while(queue.TryDequeue(out int node, out int fromKToNode)){
            if(fromKToNode > fromKToPath[node]){
                continue;
            }                     
            fromKToPath[node] = fromKToNode;
            maxPath = maxPath > fromKToNode ? maxPath : fromKToNode;
            for(var i = 0; i < adj[node].Length; i++){
                if(adj[node][i] != Int32.MaxValue &&  adj[node][i] + fromKToNode < fromKToPath[i]){
                    queue.Enqueue(i, adj[node][i] + fromKToNode);
                }
            }
        }
        return fromKToPath.Count(x=>x != Int32.MaxValue) == n ? maxPath : -1;
    }
}

寫的可能比較長，不過大致上 Dijkstra 就是這樣運作的。
雖然這題是求最短路徑中最長的路徑，但其實 Dijkstra 要求的，點 k 到其他點的最短距離我們也存在陣列 fromKToPath 了。

記得優先級佇列的優先級是起點到該點的距離，其他其實跟無權大同小異。
會說像 BFS 就是因為這個佇列的使用，和循序漸進的挑選，如果需要，我們一樣可以用雙層迴圈來標是這是第幾次的選擇(BFS 的同階段選擇)。

有一個觀念是在有向有權圖中，第一次到訪某個點並不一定是最短路徑，有可能走了比較多步的加總權重還比少步的權重低，所以我們必須要持續更新完、確認完所有可能路徑才能定論最短路徑。
相較無權圖，這也是一個差異，相對來說拜訪與否可以向這題一樣，用起點到其他點的路徑是否不為正無窮來檢查。

至此差不多圖論的基本遍歷、有向無向、有權無權圖的最短路徑相關問題都帶過一遍，儘管圖論還有其他單元，本次 30 天對圖論的著墨到這裡會先暫告一個段落。
預計剩下的天數裡，會講講貪心算法和動態規劃，都還是比較進階也比較廣的，但希望能把握時間，盡量分享這部分的綱要。