題目資訊

題目編號: 2737
題目連結: Find the Closest Marked Node
主題: Array, Graph, Heap (Priority Queue), Shortest Path

題目敘述

給你一個正整數 $n$，它是0索引的有向加權圖的節點數，還有一個0索引的二維數組 $edges$，其中 $edges[i] = [u_i, v_i, w_i]$ 表示從節點 $u_i$ 到節點 $v_i$ 有一條權重為 $w_i$ 的邊。

你也被給予了一個節點 $s$ 和一個節點數組 $marked$；你的任務是找到從 $s$ 到任何標記節點的最小距離。

返回一個整數，表示從 $s$ 到任何標記節點的最小距離，如果從 $s$ 到任何標記節點沒有路徑，則返回 $-1$。

範例 1：

輸入： $n = 4$，$edges = [[0,1,1],[1,2,3],[2,3,2],[0,3,4]]$，$s = 0$，$marked = [2,3]$
輸出： $4$
解釋： 從節點0（綠色節點）到節點2（紅色節點）有一條路徑，路徑為 $0 \to 1 \to 2$，距離為 $1 + 3 = 4$。
從節點0到節點3（紅色節點）有兩條路徑，分別是 $0 \to 1 \to 2 \to 3$ 和 $0 \to 3$，第一條路徑的距離為 $1 + 3 + 2 = 6$，第二條距離為 $4$。
它們中最小的距離是 $4$。

範例 2：

輸入： $n = 5$，$edges = [[0,1,2],[0,2,4],[1,3,1],[2,3,3],[3,4,2]]$，$s = 1$，$marked = [0,4]$
輸出： $3$
解釋： 從節點1（綠色節點）到節點0（紅色節點）沒有路徑。
從節點1到節點4（紅色節點）有一條路徑，路徑為 $1 \to 3 \to 4$，距離為 $1 + 2 = 3$。
所以答案是 $3$。

範例 3：

輸入： $n = 4$，$edges = [[0,1,1],[1,2,3],[2,3,2]]$，$s = 3$，$marked = [0,1]$
輸出： $-1$
解釋： 從節點3（綠色節點）到任何標記節點（紅色節點）都沒有路徑，所以答案是 $-1$。

約束條件：

$2 \leq n \leq 500$
$1 \leq \text{edges.length} \leq 10^4$
$\text{edges}[i].\text{length} = 3$
$0 \leq \text{edges}[i][0], \text{edges}[i][1] \leq n - 1$
$1 \leq \text{edges}[i][2] \leq 10^6$
$1 \leq \text{marked.length} \leq n - 1$
$0 \leq s, \text{marked}[i] \leq n - 1$
$s \neq \text{marked}[i]$
對於每個 $i \neq j$，$\text{marked}[i] \neq \text{marked}[j]$
圖可能有重複的邊。
圖是生成的，因此沒有自環。

直覺

此問題涉及在一個加權有向圖中找到給定節點到一組標記節點的最短路徑。對於處理加權邊和非負權重的問題，這是最短路徑演算法的典型應用，通常會使用Dijkstra演算法。目的是以最小的可能路徑權重抵達一個標記節點。如果不存在這樣的路徑，則函數應返回 -1。

解法

此方法利用了Dijkstra演算法，該演算法在有非負邊權重的圖中有效地找到從一個節點到其他節點的最短路徑。該演算法使用優先佇列（最小堆）來持續擴展成本最低的節點。以下是所提供解法中實施的詳細步驟：

圖的表示：
- 使用鄰接列表來表示圖。每個節點指向一個由對組成的列表，其中每個對由鄰居節點和連接該節點的邊的權重組成。
初始化：
- 創建一個標記節點的集合以供快速查找。
- 使用一個數組來追踪已訪問的節點。
- 初始化一個優先佇列以輔助Dijkstra演算法。在此佇列中，節點存儲為對，第一個元素是負距離（以模擬最小堆），第二個元素是節點本身。
Dijkstra演算法設置：
- 首先將起始節點以初始距離0推入優先佇列。
處理優先佇列：
- 持續提取具有最小距離的節點。由於我們最初將其距離儲存為負值，這裡需要將節點的距離轉為正數。
- 如果該節點是標記節點中的一個，則返回其距離，因為我們已找到到達標記節點的最短路徑。
- 如果該節點已經被訪問，則跳過後續處理。
- 將該節點標記為已訪問。
- 對每個相鄰節點，計算通過當前節點的距離，並將這些新的距離和節點推入優先佇列以供進一步探索。
終止條件：
- 如果優先佇列耗盡而沒有遇到標記節點，這意味著從起始節點到任何標記節點都不存在路徑。因此，函數返回 -1。

此方法依仗於優先佇列有效地以成本增加的順序進行路徑探索，從而確保找到任何標記節點的最短路徑。使用鄰接列表有助於高效遍歷鄰居，而標記節點集合提供快速驗證，使得在圖遍歷過程中能快速確認到達任一目標節點。

程式碼

C++

class Solution {
public:
    int minimumDistance(int n, vector<vector<int>>& edges, int startNode, vector<int>& markedNodes) {
        
        // 使用鄰接表儲存有權重的圖。
        vector<vector<pair<int, int>>> adjacencyList(n);
        
        // 使用集合儲存標記的節點以便快速查找。
        set<int> markedSet;
        
        // 陣列來追蹤已訪問過的節點。
        vector<bool> visited(n, false);
        
        // 以邊填充鄰接表。
        for (vector<int>& edge : edges) {
            adjacencyList[edge[0]].push_back({edge[1], edge[2]});
        }
        
        // 將標記的節點插入到標記集合中。
        for (int node : markedNodes) {
            markedSet.insert(node);
        }
        
        // Dijkstra算法的優先隊列；儲存 (負的距離, 節點) 的對。
        priority_queue<pair<int, int>> pq;
        
        // 從startNode開始搜尋，初始距離為0。
        pq.push({0, startNode});
        
        while (!pq.empty()) {
            // 獲取當前距離最小的節點。
            auto [currentLen, currentNode] = pq.top();
            pq.pop();
            
            // 檢查當前節點是否已標記；如果是，則返回距離。
            if (markedSet.count(currentNode) == 1) {
                return -currentLen;
            }
            
            // 如果該節點已被訪問，則跳過。
            if (visited[currentNode]) {
                continue;
            }
            
            // 將當前節點標記為已訪問。
            visited[currentNode] = true;
            
            // 更新所有相鄰節點的距離。
            for (pair<int, int> neighbor : adjacencyList[currentNode]) {
                // 將相鄰節點與更新的距離加入優先隊列。
                pq.push({currentLen - neighbor.second, neighbor.first});
            }
        }
        
        // 如果找不到路徑，則返回-1。
        return -1;
    }
};

Python

class Solution:
    def minimumDistance(self, n, edges, startNode, markedNodes):
        
        # 使用鄰接表來儲存帶權重的圖形。
        adjacencyList = [[] for _ in range(n)]
        
        # 使用集合來儲存標記的節點以便快速查找。
        markedSet = set()
        
        # 使用陣列來追蹤訪問過的節點。
        visited = [False] * n
        
        # 用邊來填充鄰接表。
        for edge in edges:
            adjacencyList[edge[0]].append((edge[1], edge[2]))
        
        # 將標記的節點插入標記集合中。
        for node in markedNodes:
            markedSet.add(node)
        
        # 用於Dijkstra算法的優先佇列；儲存（負距離，節點）的對。
        pq = []
        
        # 從startNode開始搜尋，初始距離為0。
        heapq.heappush(pq, (0, startNode))
        
        while pq:
            # 取得當前距離最小的節點。
            currentLen, currentNode = heapq.heappop(pq)
            
            # 檢查當前節點是否已被標記；若是，返回距離。
            if currentNode in markedSet:
                return -currentLen
            
            # 如果節點已經被訪問過則跳過。
            if visited[currentNode]:
                continue
            
            # 標記當前節點為已訪問。
            visited[currentNode] = True
            
            # 更新所有相鄰節點的距離。
            for neighbor in adjacencyList[currentNode]:
                # 將相鄰節點及更新的距離加入優先佇列。
                heapq.heappush(pq, (currentLen - neighbor[1], neighbor[0]))
        
        # 如果找不到路徑，返回-1。
        return -1

複雜度分析

時間複雜度: 演算法主要使用了Dijkstra的最短路徑算法與優先佇列。此實作的時間複雜度為 $O((V + E) \log V)$，其中 $V$ 是頂點（或節點）的數量，而 $E$ 則是邊的數量。在此情境中，$V = n$，即節點的數量，而 $E = \text{edges.length}$，即圖中邊的數量。對於每個頂點，我們可能處理其所有的邊，並且優先佇列操作的時間相對於頂點的數量是對數級別的。
空間複雜度: 空間複雜度為 $O(V + E)$，其中 $V$ 是頂點的數量，而 $E$ 則是邊的數量。圖的鄰接表表示法需要 $O(V + E)$ 的空間。此外，優先佇列在最壞情況下可能包含多達 $O(V)$ 個元素，並且輔助資料結構如 visited 陣列和 markedSet 也將佔用 $O(V)$ 的空間。

CS Note
En

Leetcode 2737. Find the Closest Marked Node

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析