題目網址：https://leetcode.cn/problems/network-delay-time/

題意：有 n 個網路節點, 標記為 1 到 n。

給一 list times, 表示訊號經過有向邊的傳遞時間。times[i] = (ui, vi, wi), 其中 ui 是起點、vi 是終點, 而 wi 是一個訊號從起點傳遞到終點的時間。

從某個節點 k 發出一個訊號, 返回需要多久才能使所有節點都收到訊號？如果不能使所有節點都收到訊號, 則返回 -1 。

Solution：

想法：利用 Dijkstra 演算法（BFS + Heap）, 而非單純 BFS, 因為 weight 有可能不為 1, 這樣會導致 BFS 所得出之答案未必為解答。步驟如下：

  • 建立 adjacent lit
  • 建立 min heap
  • 執行 BFS

➔ BFS 中得到未拜訪過的點 cur , 則 dis 必為起點 k 到 cur 的最短路徑

e.g. 下圖中, 求 1 到 2 的時間

  • 若用 BFS 求解, 則 path 為 1 ➔ 2, 得出 4
  • 正確的 path 應為 1 ➔ 3 ➔ 4 ➔ 2, 得出 3

typedef pair<int, int> pii; // {weight, next}

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        vector<vector<pii>> adj(n + 1); // adjacent list
        for (const auto& t : times) {
            adj[t[0]].emplace_back(pii{t[2], t[1]});
        }

        int res = 0;
        unordered_map<int, bool> visited;
        priority_queue<pii, vector<pii>, greater<>> pq; // min heap
        pq.emplace(pii{0, k}); // 起點為 k, 則 k -> k 的 weight = 0

        while (!pq.empty()) {
            for (int k = pq.size(); k > 0; --k) {
                // 每次取出最小的邊
                const auto [dis, cur] = pq.top();
                pq.pop();

                if (visited[cur]) { // 已拜訪則跳過
                    continue;
                }

                // 設為已拜訪, 並更新時間
                visited[cur] = true;
                res = max(res, dis);

                // 將 cur 延伸出去的所有邊加入到 pq 中
                for (const auto& [weight, next] : adj[cur]) {
                    pq.emplace(pii{dis + weight, next});
                }
            }
        }
        return (visited.size() == n) ? res : -1;
    }
};
  • time：$O(E \cdot log(E))$ ➔ Dijkstra 的時間複雜度, 因為 pq 中最多有 E 條邊, 每次 push / pop 元素需花 $O(log(E))$
  • space：$O(V + E)$ ➔ 因為 adj 為 $O(V + E)$, V 是因為要記錄所有點, E 是因為會記錄所有邊