⚠️ This visualization was AI-generated and may contain inaccuracies. Please verify against the original LeetCode problem (#743) before relying on it.

Network Delay Time

An interactive visualization of Dijkstra's algorithm for finding shortest paths in a weighted directed graph. Watch how the priority queue greedily selects the closest unvisited node and relaxes its neighbors.

Shortest Path LeetCode 743 ↗ Medium

The Problem

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 times[i] = (u_i, v_i, w_i), where u_i is the source node, v_i is the target node, and w_i is the time it takes for a signal to travel from source to target.

We will send a signal from a given node k. Return the minimum time it takes for all n nodes to receive the signal. If it is impossible for all n nodes to receive the signal, return -1.

Interactive Visualization

Number of Nodes

Edges (u,v,w per line)

Source Node (k)

Preset

Speed:

Graph Visualization

Distance Table

Priority Queue (min-heap)

Empty

Code

fun networkDelayTime(times: Array<IntArray>, n: Int, k: Int): Int {    val graph = HashMap<Int, MutableList<Pair<Int, Int>>>()    for ((u, v, w) in times)        graph.getOrPut(u) { mutableListOf() }.add(Pair(v, w))    val dist = IntArray(n + 1) { Int.MAX_VALUE }    dist[k] = 0    val pq = PriorityQueue<Pair<Int, Int>>(compareBy { it.first })    pq.add(Pair(0, k))    while (pq.isNotEmpty()) {        val (d, u) = pq.poll()        if (d > dist[u]) continue  // stale entry        for ((v, w) in graph[u] ?: emptyList()) {            if (dist[u] + w < dist[v]) {                dist[v] = dist[u] + w                pq.add(Pair(dist[v], v))            }        }    }    val mx = dist.drop(1).max()    return if (mx < Int.MAX_VALUE) mx else -1}

def networkDelayTime(times, n, k):    graph = defaultdict(list)    for u, v, w in times:        graph[u].append((v, w))    dist = {i: float('inf') for i in range(1, n + 1)}    dist[k] = 0    pq = [(0, k)]    while pq:        d, u = heapq.heappop(pq)        if d > dist[u]:  # stale entry            continue        for v, w in graph[u]:            if dist[u] + w < dist[v]:                dist[v] = dist[u] + w                heapq.heappush(pq, (dist[v], v))    mx = max(dist.values())    return mx if mx < float('inf') else -1

Status

Press Step or Play to begin.

How It Works

Key Insight

Dijkstra's algorithm is a greedy algorithm that always processes the node with the smallest known distance first (via a priority queue / min-heap). Once a node is popped from the priority queue, its shortest distance is finalized because all remaining entries in the queue have equal or greater distance. This greedy property only works when all edge weights are non-negative.

The Algorithm

Build graph: Create an adjacency list from the edge list
Initialize: Set all distances to infinity except the source node k, which gets distance 0. Push (0, k) into the priority queue.
Process: Pop the minimum-distance entry (d, u) from the priority queue
Skip stale: If d > dist[u], this is an outdated entry — skip it
Relax edges: For each neighbor v with weight w, if dist[u] + w < dist[v], update dist[v] and push (dist[v], v) into the queue
Result: The answer is the maximum distance across all nodes. If any node is still infinity, return -1 (unreachable)

Complexity

Time O(E log V)

Space O(V + E)

Each edge is relaxed at most once, and each heap operation costs O(log V). The adjacency list and distance map take O(V + E) space.