今天要來探討的是 Leetcode #743 Network Delay Time 。

方法 1 DFS

透過 DFS 來走訪，有兩個點值得提出

1. 題目給的 input 可能存在 loop ，為了避免無窮 DFS 下去，可以比對目前路線的時間花費跟之前走到此點的時間花費，若 cost 大於等於之前的 cose ，那也沒有必要再走下去。
2. 因為是 DFS 且每條 edge 所需要的時間不一樣，在從鄰點當中選出下一個要 DFS 點之前，可以先將所有鄰點依照 cost 排序過，接著選擇 cost 小的點優先做 DFS 。

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        vector<int> cost(n+1, INT_MAX);
        /* [dest, cost] */
        vector<vector<pair<int, int>>> route(n+1);
        for (auto time:times) {
            route[time[0]].push_back({time[2],time[1]});
        }
        for (int i=1; i<=n; i++) {
            sort (route[i].begin(), route[i].end());
        }
        dfs_helper (cost, route, k, 0);

        int min = 0;
        for (int i=1; i<=n; i++) {
            if (i == k) continue;
            if (cost[i] == INT_MAX) return -1;
            min = std::max (min, cost[i]);
        }
        return min;

    }
    void dfs_helper (vector<int>& cost, vector<vector<pair<int, int>>>& route,
                    int dest, int time) {
        /** 
         * Because already visited this nodes and the current cost 
         * is bigger than previous cost, we can skip this route.
         */
        if (cost[dest] <= time) return;
        cost[dest] = min(cost[dest], time);
        for (auto next_node:route[dest]) {
            dfs_helper (cost, route, next_node.second, time+next_node.first);
        }
    }
};

Time Complexity : O(N! + E log E)

一個 complete graph 有 N 個 nodes ，則可能構成 N! 可能 path 。

假設 edges 有 E 條，則 sorting 所需最大 time complexity 為 O (E log E)

Space Complexity : O (N + E)

DFS 遞迴最深為 N 層，儲存所有 edge 的花費需要 O(E)。

方法 2 Dijkstra’s Algo

Dijkstra algorithm 用來在 weighted directed graph 上找尋最短路徑，網路上有許多很好的解釋，這邊就不再描述。

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        vector<int> cost(n+1, INT_MAX);
        /* [dest, cost] */
        vector<vector<pair<int, int>>> route(n+1);
        for (auto time:times) {
            route[time[0]].push_back({time[2],time[1]});
        }

        dijikstra_helper (cost, route, k);
        int min = 0;
        for (int i=1; i<=n; i++) {
            if (i == k) continue;
            if (cost[i] == INT_MAX) return -1;
            min = std::max (min, cost[i]);
        }
        return min;

    }
    void dijikstra_helper (vector<int>& cost, vector<vector<pair<int, int>>>& route,
                    int start) {
        /* [times, dest] */
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        pq.push ({0, start});

        while (!pq.empty()) {

            int curr_time = pq.top().first;
            int curr_index = pq.top().second;
            pq.pop();
            if (curr_time > cost[curr_index]) continue;

            for (auto neighbor:route[curr_index]) {
                int neighbor_time = neighbor.first;
                int neighbor_index = neighbor.second;

                if (curr_time + neighbor_time < cost[neighbor_index]) {
                    cost[neighbor_index] =  curr_time + neighbor_time;
                    pq.push ({cost[neighbor_index], neighbor_index});
                }
            }
        }
    }
};

Time Complexity : O (E log E + N)

priority_queue 最多存放 E 個 edges ，每次對 priority_queue 的操作為 O (log E) 。

找出抵達所有節點所需最大時間需要 O(N) ， N 代表有 N 個 nodes 。

Space Complexity : O(N + E)