Skip to content

743.network-delay-time.md

Latest commit

 

History

History
572 lines (486 loc) · 18.1 KB

743.network-delay-time.md

File metadata and controls

572 lines (486 loc) · 18.1 KB

743. Network Delay Time

Key Insights

  1. To find the minimum time to reach all nodes, this is a single-source shortest path problem.
  2. The graph is directed and weighted (positive), so we can use Dijkstra's or Bellman-Ford algorithm to find the shortest path.

Dijkstra

Distance Array

Adjacency List

  • It's best fit since weights are positive.
  • Use a min heap to always process the adjacent node with the minimum time first.
  • Maintain a time array to store the shortest known time from source to each node.
data class Edge(
    val time: Int,
    val node: Int
)

fun networkDelayTime(times: Array<IntArray>, n: Int, k: Int): Int {
    val graph = buildGraph(times, n) // O(E) to build adjacency list
    val time = IntArray(n + 1) { Int.MAX_VALUE } // 1-based index, O(V)
    val minHeap = PriorityQueue(compareBy<Pair<Int, Int>> { it.first })
    time[k] = 0
    minHeap.add(0 to k) // O(log V)
    while (minHeap.isNotEmpty()) { // O(V) iterations
        val (t, node) = minHeap.poll() // O(log V)
        if (time[node] < t) continue
        graph[node].forEach { adj -> // O(E) iterations
            if (time[adj.node] > time[node] + adj.time) {
                time[adj.node] = time[node] + adj.time
                minHeap.add(time[adj.node] to adj.node) // O(log V)
            }
        }
    }
    // O(V)
    var ans = 0
    for (node in 1..n) {
        if (time[node] == Int.MAX_VALUE) return -1
        ans = maxOf(ans, time[node])
    }
    return ans
}

private fun buildGraph(times: Array<IntArray>, n: Int): Array<HashSet<Edge>> {
    val graph = Array<HashSet<Edge>>(n + 1) { hashSetOf<Edge>() }
    for ((from, to, time) in times) {
        graph[from].add(Edge(time, to))
    }
    return graph
}

Adjacency Matrix

We use adjacency matrix to build the graph:

fun dijkstraAdjacencyMatrix(times: Array<IntArray>, n: Int, k: Int): Int {
    // -1 means no edge, we have to check the possible range of weight and choose the proper value to indicate no edge.
    val adjMatrix = Array(n + 1) { IntArray(n + 1) { -1 } }
    for ((from, to, time) in times) {
        adjMatrix[from][to] = time
    }
    val time = IntArray(n + 1) { Int.MAX_VALUE }
    val minHeap = PriorityQueue(compareBy<Pair<Int, Int>> { it.first } )
    time[k] = 0
    minHeap.add(0 to k)
    while (minHeap.isNotEmpty()) {
        val (t, node) = minHeap.poll()
        if (time[node] < t) continue
        for (adjNode in adjMatrix[node].indices) {
            val adjTime = adjMatrix[node][adjNode]
            // We have to skip the edge if it doesn't exist.
            if (adjTime == -1) continue
            if (time[adjNode] > time[node] + adjTime) {
                time[adjNode] = time[node] + adjTime
                minHeap.add(time[adjNode] to adjNode)
            }
        }
    }
    var ans = 0
    for (node in 1..n) {
        if (time[node] == Int.MAX_VALUE) return -1
        ans = maxOf(ans, time[node])
    }
    return ans
}
  • Time Complexity: O((V + E) log V)
    • Build graph: O(E).
    • Main loop: O((V + E) log V).
      • Heap operations: Each node can be popped at most once, so O(V log V) for all poll().
      • Edge processing: Each edge can be processed at most once per node, so O(E log V) for all add().
    • Find the answer: O(V).
  • Space Complexity: O(V + E) or O(V^2)
    • Build graph: O(V + E) for adjacency list, O(V^2) for adjacency matrix.
    • Time array: O(V).
    • Min heap: O(V).

Visited Set

It's a variant of Dijkstra's algorithm without changing the core Dijkstra's invariant: the first time we visit a node pop from the heap, we have found its shortest distance.

There are some key differences from above implementation and the "textbook" Dijkstra's algorithm:

  1. Marking visited on pop instead of on push, this ensures us finalize a node exactly once, at its true shortest distance.
  2. Not maintaining a time array (distance array):
    • We allow duplicate, it's OK to push the same node multiple times with different distance.
    • We us visited to discard stale entries: The first time a node entry popped from min heap is the shortest (positive weight); later duplicate entries are skipped by visited set.
  3. time (answer) ends up being the largest time of finalized shortest distance, all nodes are popped in non-decreasing order of time, the last pop is the largest time.
fun dijkstra(times: Array<IntArray>, n: Int, k: Int): Int {
    val graph = buildGraph(times, n)
    var remainingN = n
    var time = 0
    val visited = BooleanArray(n + 1) // O(V)
    val minHeap = PriorityQueue<Pair<Int, Int>>(compareBy { it.first })
    minHeap.add(0 to k)
    while (minHeap.isNotEmpty()) {
        val (t, node) = minHeap.poll() // O(log E)
        // We must skip the visited (stale) node first
        if (visited[node]) {
            continue
        }
        visited[node] = true 
        time = maxOf(t, time) // Or we just update time = t directly, the first time we visit a node is the shortest path.
        remainingN--
        graph[node].forEach { (adjNode, adjTime) -> // O(E)
            minHeap.add((adjTime + t) to adjNode)   // O(log E)
        }
    }
    return if (remainingN == 0) time else -1
}
  • Time Complexity: O((V + E) log E) on average or O(E log E) in the worst case (dense graph, E = V^2)
    • Build graph: O(E).
    • Main loop: O((V + E) log E)
      • Heap can contain up to O(E) entries since we always enqueue ALL neighbors for each node.
      • Heap operations: Each node can be popped at most once, so O(V log E) for all poll().
      • Edge processing: We enqueue all edges for each node, so O(E log E) for all add().
    • Find the answer: O(V).
  • Space Complexity: O(V + E), O(V^2) for adjacency matrix.
    • Build graph: O(V + E) for adjacency list, O(V^2) for adjacency matrix.
    • Visited set: O(V).
    • Min heap: O(E).

Dry Run

 A -- (1)--> B
 |         /
(2)       /
 |       /
 C <-- (5)
  • We have two entries for C: 2 and 6.
  • We visit C at distance 2 first, which is the true shortest path.
  • The later entry 6 is discarded because we have already visited C at distance 2.
  • The final answer is 2.
 A -- (1)--> B
 |         /
(5)       /
 |       /
 C <-- (2)
  • We enqueued C twice: once with 5 (direct) and later with 3 (via B).
  • We visit C at distance 3 first, becase we pop the shorter entry (3 to C) over the longer entry (5 to C) from the min heap.
  • Mark C as visited.
  • The later entry 5 is discarded because we have already visited C at distance 3.
  • The final answer is 3.

Shortest Path Faster Algorithm

TODO: Review the notes + implementations

fun spfa(times: Array<IntArray>, n: Int, k: Int): Int {
    val graph = buildGraph(times, n)
    val queue = ArrayDeque<Int>() // We use queue, not min heap.
    val time = IntArray(n + 1) { Int.MAX_VALUE }
    time[k] = 0
    queue.add(k)
    while (queue.isNotEmpty()) {
        val node = queue.removeFirst()
        graph[node].forEach { (adjTime, adjNode) ->
            // We relax the edge and enqueue the adjacent node, if the new distance is shorter.
            if (time[adjNode] > time[node] + adjTime) {
                time[adjNode] = time[node] + adjTime
                queue.addLast(adjNode)
            }
        }
    }
    var ans = 0
    for (node in 1..n) {
        if (time[node] == Int.MAX_VALUE) return -1
        ans = maxOf(ans, time[node])
    }
    return ans
}

Bellman-Ford Algorithm

TODO: Review the notes + implementations

fun networkDelayTime(times: Array<IntArray>, n: Int, k: Int): Int {
    // Here we won't use Int.MAX_VALUE because it will break the relaxation, since Int.MAX_VALUE + any number will be Int.MIN_VALUE, it makes the result wrong.
    val infinite = Int.MAX_VALUE / 2
    val times = IntArray(n + 1) { _ -> infinite }
    times[k] = 0

    for (i in 1..n - 1) {
        for (edge in times) {
            val u = edge[0]
            val v = edge[1]
            val weight = edge[2]
            if (times[v] > times[u] + weight) {
                times[v] = times[u] + weight
            }
        }
    }

    var max = Int.MIN_VALUE
    for (vertex in 1..n) {
        val d = times[vertex]
        max = if (d > max) d else max
    }
    return if (max == infinite) -1 else max
}

References

The following implementations are from LeetCode solutions.

Variant 1: Heap Value Only + Visited Set

Key Pattern: Uses popped heap value directly, no distance array

public int networkDelayTime(int[][] times, int N, int K) {
    Map<Integer, Map<Integer,Integer>> map = new HashMap<>();
    for(int[] time : times){
        map.putIfAbsent(time[0], new HashMap<>());
        map.get(time[0]).put(time[1], time[2]);
    }

    //distance, node into pq
    Queue<int[]> pq = new PriorityQueue<>((a,b) -> (a[0] - b[0]));

    pq.add(new int[]{0, K});

    boolean[] visited = new boolean[N+1];
    int res = 0;

    while(!pq.isEmpty()){
        int[] cur = pq.remove();
        int curNode = cur[1];
        int curDist = cur[0];
        if(visited[curNode]) continue;
        visited[curNode] = true;
        res = curDist;  // Uses popped value directly
        N--;
        if(map.containsKey(curNode)){
            for(int next : map.get(curNode).keySet()){
                pq.add(new int[]{curDist + map.get(curNode).get(next), next});
            }
        }
    }
    return N == 0 ? res : -1;
}

Variant 2: Distance Array + Visited Set (Standard)

Key Pattern: Classic Dijkstra with both distance array and visited set

typedef pair<int, int> pii;

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        vector<vector<pii> > g(n + 1);
        for (const auto& t : times) {
            g[t[0]].emplace_back(t[1], t[2]);
        }
        const int inf = 1e9;
        vector<int> dist(n + 1, inf);
		vector<bool> vis(n + 1, false);
        dist[k] = 0;
        priority_queue<pii, vector<pii>, greater<pii> > pq;
        pq.emplace(0, k);
        int u, v, w;
        while (!pq.empty()) {
            u = pq.top().second; pq.pop();
			if (vis[u]) continue;
			vis[u] = true;
            for (auto& to : g[u]) {
                v = to.first, w = to.second;
                if (dist[v] > dist[u] + w) {
                    dist[v] = dist[u] + w;
                    pq.emplace(dist[v], v);
                }
            }
        }
        int ans = *max_element(dist.begin() + 1, dist.end());
        return ans == inf ? -1 : ans;
    }
};

Variant 3: Distance Array + Visited Set + Conservative Enqueuing

Key Pattern: Checks visited and distance before enqueuing (reduces heap size)

public int networkDelayTime_Dijkstra(int[][] times, int N, int K) {
    Map<Integer, List<int[]>> graph = new HashMap<>();
    for (int[] edge: times) {
        graph.putIfAbsent(edge[0], new ArrayList<>());
        graph.get(edge[0]).add(new int[]{edge[1], edge[2]});
    }
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> (a[0] - b[0]));
    boolean[] visited = new boolean[N + 1];
    int[] minDis = new int[N + 1];
    Arrays.fill(minDis, Integer.MAX_VALUE);
    minDis[K] = 0;
    pq.offer(new int[]{0, K});
    int max = 0;
    while (!pq.isEmpty()) {
        int[] curr = pq.poll();
        int currNode = curr[1];
        if (visited[currNode]) continue;
        visited[currNode] = true;
        int currDis = curr[0];
        max = currDis;
        N--;
        if (!graph.containsKey(currNode)) continue;
        for (int[] next : graph.get(currNode)) {
            if (!visited[next[0]] && currDis + next[1] < minDis[next[0]])  // Conservative check
                pq.offer(new int[]{currDis + next[1], next[0]});
        }
    }
    return N == 0 ? max : -1;
}

Variant 4: Distance Array + Visited Set

void dijkstra() {
    // 起始先将所有的点标记为「未更新」和「距离为正无穷」
    Arrays.fill(vis, false);
    Arrays.fill(dist, INF);
    // 只有起点最短距离为 0
    dist[k] = 0;
    // 使用「优先队列」存储所有可用于更新的点
    // 以 (点编号, 到起点的距离) 进行存储，优先弹出「最短距离」较小的点
    PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->a[1]-b[1]);
    q.add(new int[]{k, 0});
    while (!q.isEmpty()) {
        // 每次从「优先队列」中弹出
        int[] poll = q.poll();
        int id = poll[0], step = poll[1];
        // 如果弹出的点被标记「已更新」，则跳过
        if (vis[id]) continue;
        // 标记该点「已更新」，并使用该点更新其他点的「最短距离」
        vis[id] = true;
        for (int i = he[id]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[id] + w[i]) {
                dist[j] = dist[id] + w[i];
                q.add(new int[]{j, dist[j]});
            }
        }
    }
}

问：为什么代码要判断 dx > dis[x]？

答：对于同一个 x，例如先入堆一个比较大的 dis[x]=10，后面又把 dis[x] 更新成 5，之后这个 5 会先出堆，然后再把 10 出堆。10 出堆时候是没有必要去更新周围邻居的最短路的，因为 5 出堆之后，就已经把邻居的最短路更新过了，用 10 是无法把邻居的最短路变得更短的，所以直接 continue。

Variant 5: Distance Array + Distance Check (Most Common)

Key Pattern: Uses distance check instead of visited set (most interview-friendly)

def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
    g = [[] for _ in range(n)]  # 邻接表
    for x, y, d in times:
        g[x - 1].append((y - 1, d))

    dis = [inf] * n
    dis[k - 1] = 0
    h = [(0, k - 1)]
    while h:
        dx, x = heappop(h)
        if dx > dis[x]:  # x 之前出堆过
            continue
        for y, d in g[x]:
            new_dis = dx + d
            if new_dis < dis[y]:
                dis[y] = new_dis  # 更新 x 的邻居的最短路
                heappush(h, (new_dis, y))
    mx = max(dis)
    return mx if mx < inf else -1
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
    g = [[] for _ in range(n)]
    for x, y, time in times:
        g[x - 1].append((y - 1, time))

    dist = [float('inf')] * n
    dist[k - 1] = 0
    q = [(0, k - 1)]
    while q:
        time, x = heapq.heappop(q)
        if dist[x] < time:
            continue
        for y, time in g[x]:
            if (d := dist[x] + time) < dist[y]:
                dist[y] = d
                heapq.heappush(q, (d, y))

    ans = max(dist)
    return ans if ans < float('inf') else -1

Variant 7: Naive 樸素 Dijkstra

Key Pattern: Traditional Dijkstra without heap, scans all nodes each iteration

public int networkDelayTime(int[][] times, int n, int k) {
    final int INF = Integer.MAX_VALUE / 2; // 防止加法溢出
    int[][] g = new int[n][n]; // 邻接矩阵
    for (int[] row : g) {
        Arrays.fill(row, INF);
    }
    for (int[] t : times) {
        g[t[0] - 1][t[1] - 1] = t[2];
    }

    int maxDis = 0;
    int[] dis = new int[n];
    Arrays.fill(dis, INF);
    dis[k - 1] = 0;
    boolean[] done = new boolean[n];
    while (true) {
        int x = -1;
        for (int i = 0; i < n; i++) {
            if (!done[i] && (x < 0 || dis[i] < dis[x])) {
                x = i;
            }
        }
        if (x < 0) {
            return maxDis; // 最后一次算出的最短路就是最大的
        }
        if (dis[x] == INF) { // 有节点无法到达
            return -1;
        }
        maxDis = dis[x]; // 求出的最短路会越来越大
        done[x] = true; // 最短路长度已确定（无法变得更小）
        for (int y = 0; y < n; y++) {
            // 更新 x 的邻居的最短路
            dis[y] = Math.min(dis[y], dis[x] + g[x][y]);
        }
    }
}

Implementation Variants Summary

1. Distance Array vs Heap Value Only

Distance Array Approach:

// Your current implementation
val time = IntArray(n + 1) { Int.MAX_VALUE }
// ... process and update time array
var ans = 0
for (node in 1..n) {
    if (time[node] == Int.MAX_VALUE) return -1
    ans = maxOf(ans, time[node])
}

Heap Value Only Approach:

// Alternative approach
var time = 0
while (minHeap.isNotEmpty()) {
    val (t, node) = minHeap.poll()
    if (visited[node]) continue
    visited[node] = true
    time = t  // Use popped value directly
    // ... process neighbors
}

  • Key Insight: Both work because Dijkstra processes nodes in non-decreasing order of distance. The last processed node will have the maximum distance.

  • Recommendation: Use Distance Array for interviews - it's more explicit and what interviewers expect.

2. Visited Set vs Distance Check

Visited Approach:

val visited = BooleanArray(n + 1)
// ... in loop
if (visited[node]) continue
visited[node] = true

Distance Check Approach:

// Alternative approach
if (time[node] < t) continue

  • Key Insight: Both achieve the same goal - ensuring each node is processed exactly once at its shortest distance. The distance check is more efficient as it doesn't require an extra array.

  • Recommendation: Use Distance Check (if (time[node] < t) continue) - it's the most common pattern in LeetCode solutions.

3. Relaxation Check Timing

Conservative (Before Enqueuing):

graph[node].forEach { adj ->
    if (!visited[adj.node] && time[node] + adj.time < time[adj.node]) {
        time[adj.node] = time[node] + adj.time
        minHeap.add(adj.node to time[adj.node])
    }
}

Lazy (Always Enqueue):

graph[node].forEach { adj ->
    minHeap.add(adj.node to time[adj.node])
}

  • Key Insight: The lazy approach is simpler and still correct because the distance check on pop (if (time[node] < t) continue) handles stale entries.

  • Recommendation: Use Lazy Enqueuing - always enqueue and let the distance check handle stale entries.

Summary

All variants are correct because they respect Dijkstra's fundamental property: the first time a node is popped from the min-heap, we have found its shortest distance.