Advanced Graphs

LeetCode 743

LeetCode #743Difficulty: MediumNeetCode 150

LeetCode 743: Network Delay Time

LeetCode

Calculate minimum time for all nodes to receive a signal using Dijkstra's Algorithm.

Problem Description

You are given a network of `n` nodes, labeled from `1` to `n`. You are also given `times`, a list of travel times as directed edges. Return the minimum time it takes for all the `n` nodes to receive the signal.

Examples:
Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2
Constraints:
  • 1 <= k <= n <= 100
  • 1 <= times.length <= 6000

Core Mental Model

Dijkstra's greedy expansion: always visit the unvisited node with the smallest cumulative distance using a Min-Heap. Update neighbor distances if shorter path discovered.

Formal Loop Invariant

Invariant: When a node is popped from the min-heap, its shortest path distance is permanently settled.

Key Architectural Takeaway:

Dijkstra guarantees shortest paths in non-negative weighted graphs in O(E log V) time.

Asymptotic Complexity Analysis

Time ComplexityO(E log V)Linear scan
Space ComplexityO(V + E) adjacency list & min-heap.Constant auxiliary

Bottleneck: Heap operations per edge.

Edge Cases & Screener Traps

  • Disconnected graph (unreachable nodes return -1)