Network Delay Time (Dijkstra)

▶

Steps

setup

Initialize distances

Set initial distances to all nodes as infinity except the source node 2, which is set to 0.

💡 This sets the starting point for shortest path calculations, marking the source as reachable immediately.

Line:

dist = [float('inf')] * (n + 1)
dist[k] = 0

💡 Distances array holds the best known shortest times from source to each node.

fill_row

Start first iteration of edge relaxation

Begin the first of n-1 iterations to relax edges and update distances.

💡 Each iteration tries to improve shortest paths by checking all edges.

Line:

for _ in range(n - 1):
    updated = False

💡 The algorithm will attempt to relax edges multiple times to propagate shortest paths.

fill_cells

Relax edge (2 -> 1)

Check if distance to node 1 can be improved via node 2. Current dist[2] + weight = 0 + 1 = 1 < ∞, so update dist[1] to 1.

💡 Relaxing edges updates shortest known distances when a better path is found.

Line:

for u, v, w in times:
    if dist[u] != float('inf') and dist[u] + w < dist[v]:
        dist[v] = dist[u] + w
        updated = True

💡 Relaxation improves shortest path estimates by considering new routes.

fill_cells

Relax edge (2 -> 3)

Check if distance to node 3 can be improved via node 2. Current dist[2] + weight = 0 + 1 = 1 < ∞, so update dist[3] to 1.

💡 Relaxing multiple edges from the source spreads shortest path info to neighbors.

Line:

for u, v, w in times:
    if dist[u] != float('inf') and dist[u] + w < dist[v]:
        dist[v] = dist[u] + w
        updated = True

💡 Multiple neighbors can be updated in the same iteration if reachable.

fill_cells

Relax edge (3 -> 4)

Check if distance to node 4 can be improved via node 3. Current dist[3] is ∞ at this moment, so no update.

💡 Edges from nodes not yet updated cannot improve distances yet.

Line:

for u, v, w in times:
    if dist[u] != float('inf') and dist[u] + w < dist[v]:
        dist[v] = dist[u] + w
        updated = True

💡 Relaxation depends on current known distances; unreachable nodes don't improve others yet.

fill_row

End of first iteration

First iteration completed with updates to nodes 1 and 3 distances. Prepare for second iteration.

💡 Multiple iterations are needed to propagate distance improvements through the graph.

Line:

if not updated:
    break

💡 Algorithm continues because improvements were made.

fill_row

Start second iteration of edge relaxation

Begin second iteration to try relaxing edges again to improve distances further.

💡 Subsequent iterations propagate improvements through longer paths.

Line:

for _ in range(n - 1):
    updated = False

💡 Relaxation attempts continue until no improvements occur.

fill_cells

Relax edge (2 -> 1) again

Check if distance to node 1 can be improved via node 2 again. Current dist[1] = 1, new possible = 0 + 1 = 1, no improvement.

💡 Repeated relaxation checks confirm if distances can still improve.

Line:

for u, v, w in times:
    if dist[u] != float('inf') and dist[u] + w < dist[v]:
        dist[v] = dist[u] + w
        updated = True

💡 No improvement means shortest path to node 1 is already found.

fill_cells

Relax edge (2 -> 3) again

Check if distance to node 3 can be improved via node 2 again. Current dist[3] = 1, new possible = 0 + 1 = 1, no improvement.

💡 Repeated checks ensure no shorter paths are missed.

Line:

for u, v, w in times:
    if dist[u] != float('inf') and dist[u] + w < dist[v]:
        dist[v] = dist[u] + w
        updated = True

💡 Distance to node 3 is already optimal.

fill_cells

Relax edge (3 -> 4) now reachable

Check if distance to node 4 can be improved via node 3. Current dist[3] = 1, new possible = 1 + 1 = 2 < ∞, update dist[4] to 2.

💡 Now that node 3 has a known distance, its edges can improve others.

Line:

for u, v, w in times:
    if dist[u] != float('inf') and dist[u] + w < dist[v]:
        dist[v] = dist[u] + w
        updated = True

💡 Distances propagate through the graph as nodes become reachable.

fill_row

End of second iteration

Second iteration completed with update to node 4 distance. Prepare for third iteration.

💡 Further iterations check if any more improvements are possible.

Line:

if not updated:
    break

💡 Distances continue to improve until stable.

fill_row

Start third iteration

Begin third iteration to check for any further distance improvements.

💡 Algorithm ensures no shorter paths remain after n-1 iterations.

Line:

for _ in range(n - 1):
    updated = False

💡 If no updates occur, algorithm will stop early.

fill_cells

Relax edge (2 -> 1) no update

Check edge (2 -> 1) again. No improvement since dist[1] = 1 and 0 + 1 = 1.

💡 Repeated checks confirm distances are stable.

Line:

for u, v, w in times:
    if dist[u] != float('inf') and dist[u] + w < dist[v]:
        dist[v] = dist[u] + w
        updated = True

💡 No further improvements possible on this edge.

fill_cells

Relax edge (2 -> 3) no update

Check edge (2 -> 3) again. No improvement since dist[3] = 1 and 0 + 1 = 1.

💡 No changes means distances are stable.

Line:

for u, v, w in times:
    if dist[u] != float('inf') and dist[u] + w < dist[v]:
        dist[v] = dist[u] + w
        updated = True

💡 No further improvements possible on this edge.

fill_cells

Relax edge (3 -> 4) no update

Check edge (3 -> 4) again. No improvement since dist[4] = 2 and 1 + 1 = 2.

💡 No updates means shortest paths are finalized.

Line:

for u, v, w in times:
    if dist[u] != float('inf') and dist[u] + w < dist[v]:
        dist[v] = dist[u] + w
        updated = True

💡 All shortest distances are stable now.

prune

No updates in third iteration, algorithm stops

Since no distances were updated in this iteration, the algorithm terminates early.

💡 Early stopping improves efficiency when no further improvements are possible.

Line:

if not updated:
    break

💡 Shortest paths have been found for all reachable nodes.

reconstruct

Compute final answer

Calculate the maximum distance among all nodes to determine the network delay time.

💡 The maximum shortest distance is the time for the signal to reach all nodes.

Line:

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

💡 The answer represents the longest shortest path from source to any node.

def network_delay_time(times, n, k):
    dist = [float('inf')] * (n + 1)  # STEP 1 initialize distances
    dist[k] = 0  # STEP 1 source distance zero
    for _ in range(n - 1):  # STEP 2 start iterations
        updated = False  # STEP 2 reset update flag
        for u, v, w in times:  # STEP 3-15 relax each edge
            if dist[u] != float('inf') and dist[u] + w < dist[v]:  # STEP 3-15 check relaxation
                dist[v] = dist[u] + w  # STEP 3-15 update distance
                updated = True  # STEP 3-15 mark updated
        if not updated:  # STEP 16 break if no updates
            break
    ans = max(dist[1:])  # STEP 17 compute answer
    return ans if ans < float('inf') else -1  # STEP 17 return result

if __name__ == '__main__':
    times = [[2,1,1],[2,3,1],[3,4,1]]
    n = 4
    k = 2
    print(network_delay_time(times, n, k))

📊

Network Delay Time (Dijkstra) - Watch the Algorithm Execute, Step by Step

Watching each relaxation step reveals how shortest paths are progressively improved, making the algorithm's logic clear without needing to read code.

Visiting: none

1

2

3

4

Visiting: none

1

2

3

4

Visiting: 2

Edge: 2 → 1

1

2

3

4

Visiting: 2

Edge: 2 → 3

1

2

3

4

Visiting: 3

Edge: 3 → 4

1

2

3

4

Visiting: none

1

2

3

4

Visiting: none

1

2

3

4

Visiting: 2

Edge: 2 → 1

1

2

3

4

Visiting: 2

Edge: 2 → 3

1

2

3

4

Visiting: 3

Edge: 3 → 4

1

2

3

4

Visiting: none

1

2

3

4

Visiting: none

1

2

3

4

Visiting: 2

Edge: 2 → 1

1

2

3

4

Visiting: 2

Edge: 2 → 3

1

2

3

4

Visiting: 3

Edge: 3 → 4

1

2

3

4

Visiting: none

1

2

3

4

Visiting: none

1

2

3

4

Key Takeaways

✓ Bellman-Ford relaxes edges repeatedly to propagate shortest path information through the graph.

This iterative relaxation is hard to visualize from code alone but becomes clear when watching each edge update.

✓ Distances only improve when a shorter path is found, and no updates means the algorithm can stop early.

Early stopping is a key optimization that is easier to understand when seeing the update flag in action.

✓ The maximum shortest distance after all relaxations represents the network delay time to reach all nodes.

Understanding that the answer is the longest shortest path is clearer when seeing all distances finalized visually.

Practice

1. You are given an undirected graph with n nodes and a list of edges. The task is to find how many groups of nodes exist such that each group is fully connected internally and disconnected from other groups. Which algorithmic approach guarantees an optimal solution to this problem?

easy

A. Graph traversal using BFS or DFS to explore connected components

B. Dynamic Programming with memoization to count connected subgraphs

C. Greedy algorithm selecting edges to maximize connectivity

D. Topological sorting to order nodes and count components

Solution

1. Step 1: Understand the problem as counting connected components in an undirected graph

   Counting connected components requires visiting all nodes reachable from a starting node before moving to the next unvisited node.

2. Step 2: Identify BFS or DFS as the standard approach to explore all nodes in a component efficiently

   BFS or DFS traverses all nodes in a component in O(n + e) time, ensuring all connected nodes are counted once.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   BFS/DFS is the classic method for connected components [OK]

Hint: Connected components require graph traversal [OK]

Common Mistakes:

• Confusing with DP or greedy approaches that don't guarantee full exploration

2. You are given a start word, an end word, and a dictionary of words. You can change one letter at a time, and each intermediate word must be in the dictionary. Which algorithmic approach guarantees finding the shortest transformation sequence from start to end word?

easy

A. Depth-First Search exploring all possible transformations

B. Breadth-First Search on an implicit graph of words differing by one letter

C. Greedy algorithm changing letters to match the end word as fast as possible

D. Dynamic Programming storing minimum transformations for each prefix

Solution

1. Step 1: Model the problem as shortest path in a graph

   The problem can be represented as a graph where each node is a word, and edges connect words differing by one letter.

2. Step 2: Identify the algorithm that finds shortest paths in unweighted graphs

   Breadth-First Search (BFS) explores neighbors level by level, guaranteeing the shortest path length.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   BFS finds shortest paths in unweighted graphs [OK]

Hint: Shortest path in unweighted graph -> BFS [OK]

Common Mistakes:

• Thinking DFS finds shortest path
• Using greedy letter changes
• Applying DP without graph structure

3. Consider the following buggy code snippet for the 01 Matrix problem. Which line contains the subtle bug that can cause incorrect distances or runtime errors?

medium

A. Line initializing dist with float('inf')

B. Line setting dist[i][j] = 0 when mat[i][j] == 0

C. Line with 'if i >= 0:' condition

D. Line with 'if j < n - 1:' condition in backward pass

Solution

1. Step 1: Analyze the condition 'if i >= 0:'

   This condition is always true for i in range(m), so dist[i-1][j] access is unsafe when i=0 (index -1).

2. Step 2: Identify the bug

   Accessing dist[-1][j] causes incorrect behavior or runtime error; correct condition should be 'if i > 0:'.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Boundary check off-by-one leads to invalid index [OK]

Hint: Check boundary conditions carefully to avoid invalid indices [OK]

Common Mistakes:

• Off-by-one in boundary checks
• Incorrect initialization
• Misplaced conditions

4. Examine the following buggy flood fill code snippet. Which line contains the subtle bug that can cause infinite recursion or incorrect behavior?

medium

A. Line 6: checking if image[r][c] == newColor before recoloring

B. Line 2: missing check if original_color == newColor before starting

C. Line 8: recoloring pixel before checking neighbors

D. Line 11: boundary check for neighbors

Solution

1. Step 1: Identify missing early exit condition

   The code does not check if the starting pixel's color equals newColor before DFS, which can cause infinite recursion if they are equal.

2. Step 2: Verify other lines

   Line 6's check prevents revisiting recolored pixels, line 8 recolors before neighbors which is correct, and line 11 correctly checks boundaries.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Missing early exit causes infinite recursion on equal colors [OK]

Hint: Check if start pixel color equals newColor before DFS [OK]

Common Mistakes:

• Forgetting early exit causes infinite recursion
• Misplacing boundary checks

5. Suppose the graph nodes can be reused in multiple disconnected components, and the input to cloneGraph is a list of nodes representing multiple disconnected graphs. Which modification to the BFS-based cloneGraph algorithm correctly handles cloning all components without duplicating nodes or missing any?

hard

A. Initialize a global visited map and run BFS starting from each node in the list, skipping nodes already visited.

B. Run cloneGraph separately on each node in the list without tracking visited nodes globally.

C. Modify cloneGraph to clone only the first node and ignore others, assuming all are connected.

D. Use node values as keys in visited map to avoid revisiting nodes across components.

Solution

1. Step 1: Understand the problem with multiple disconnected components

   Cloning must cover all components without duplicating nodes shared across components.

2. Step 2: Modify BFS to handle multiple start nodes with global visited

   Use a global visited map and run BFS from each node in the input list, skipping nodes already cloned to avoid duplicates.

3. Step 3: Reject incorrect approaches

   Running cloneGraph separately without global visited causes duplicates; using node values as keys fails with duplicate values.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Global visited map prevents duplicates across components [OK]

Hint: Use global visited map when cloning multiple components [OK]

Common Mistakes:

• Running BFS separately without global visited causes duplicates
• Using node values as keys breaks cloning correctness