Network Delay Time and Path Reconstruction
Solve network-delay-time with Dijkstra, reconstruct the actual shortest path using a predecessor map, and discuss bidirectional BFS for large graphs.
Network Delay Time and Path Reconstruction is a free DSA Interview Prep lesson on CoddyKit — lesson 4 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
Network Delay Time Problem
Network Delay Time (LeetCode 743): given a network of n nodes and directed weighted edges representing signal travel times, find the minimum time for a signal sent from node k to reach all nodes. If some node is unreachable, return -1. This is a direct application of Dijkstra: the answer is the maximum shortest-path distance from k across all nodes.
Solution: Dijkstra + Max of Distances
Run Dijkstra from source k to find dist[v] for all nodes v. The answer is max(dist.values()). If any dist[v] is still inf, that node is unreachable — return -1. The signal travels all paths simultaneously, so the bottleneck is the node that takes the longest to reach.
import heapq
from collections import defaultdict
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
heap = [(0, k)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]:
continue
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heapq.heappush(heap, (dist[v], v))
ans = max(dist.values())
return ans if ans < float('inf') else -1
print(networkDelayTime([[2,1,1],[2,3,1],[3,4,1]], 4, 2)) # 2Path Reconstruction with prev Array
To reconstruct the actual shortest path alongside computing distances, maintain a prev dictionary that records the best predecessor for each node. Whenever we update dist[v], set prev[v] = u. After Dijkstra finishes, trace backwards from the destination through prev pointers until the source is reached, then reverse to get the forward path.
import heapq
from collections import defaultdict
def shortest_path_with_reconstruction(times, n, src, dst):
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)}
prev = {i: None for i in range(1, n+1)}
dist[src] = 0
heap = [(0, src)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]: continue
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
prev[v] = u
heapq.heappush(heap, (dist[v], v))
# Reconstruct path from src to dst
path, node = [], dst
while node is not None:
path.append(node)
node = prev[node]
return dist[dst], path[::-1]Bidirectional BFS for Large Unweighted Graphs
For large unweighted graphs where only one source-destination pair is needed, Bidirectional BFS can be significantly faster than standard BFS. It simultaneously runs BFS from the source and from the destination, stopping when the two frontiers meet. The practical speedup is significant because each frontier only needs to explore half the graph depth — reducing explored nodes from O(b^d) to O(2 × b^(d/2)) where b is branch factor.
from collections import deque
def bidir_bfs(graph, src, dst):
if src == dst: return 0
front_q = deque([src]); front_visited = {src: 0}
back_q = deque([dst]); back_visited = {dst: 0}
def expand(queue, visited, other_visited):
node = queue.popleft()
for nxt in graph[node]:
if nxt not in visited:
visited[nxt] = visited[node] + 1
queue.append(nxt)
if nxt in other_visited:
return visited[nxt] + other_visited[nxt]
return -1
while front_q or back_q:
res = expand(front_q, front_visited, back_visited)
if res != -1: return res
res = expand(back_q, back_visited, front_visited)
if res != -1: return res
return -1When to Choose Which Algorithm
Decision guide: Unweighted graph, single pair → BFS or Bidirectional BFS. Weighted, non-negative, single source → Dijkstra. Weighted, possibly negative, single source → Bellman-Ford. All pairs → Floyd-Warshall (small V) or V × Dijkstra (sparse). Constrained hops → Modified Bellman-Ford with limited passes. Stating this decision rationale aloud in interviews demonstrates algorithmic maturity.
Find the City With the Fewest Reachable Neighbours (LeetCode 1334)
Given cities with weighted paths and a distanceThreshold, find the city reachable from the fewest other cities within the threshold (prefer the larger city index on ties). Solution: compute all-pairs shortest paths with Floyd-Warshall, then for each city count how many other cities are reachable within the threshold. Return the city with the minimum count (ties: maximum index).
def findTheCity(n, edges, distanceThreshold):
INF = float('inf')
dist = [[INF]*n for _ in range(n)]
for i in range(n): dist[i][i] = 0
for u, v, w in edges:
dist[u][v] = dist[v][u] = w
for k in range(n):
for i in range(n):
for j in range(n):
dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
best_city, best_count = -1, n
for city in range(n):
count = sum(1 for j in range(n) if j != city and dist[city][j] <= distanceThreshold)
if count <= best_count:
best_count = count
best_city = city
return best_city
print(findTheCity(4,[[0,1,3],[1,2,1],[1,3,4],[2,3,1]],4)) # 3Path in a Weighted DAG
For a Directed Acyclic Graph (DAG), shortest (or longest) paths can be found by topological sort + relaxation in O(V+E) — faster than Dijkstra. Process nodes in topological order; when processing node u, relax all outgoing edges. For longest paths (useful in project scheduling / critical path), negate weights or change min to max.
from collections import deque
def dag_shortest_path(V, edges, source):
graph = [[] for _ in range(V)]
in_degree = [0] * V
for u, v, w in edges:
graph[u].append((v, w))
in_degree[v] += 1
# Topological sort (Kahn's)
queue = deque(i for i in range(V) if in_degree[i] == 0)
topo = []
while queue:
node = queue.popleft(); topo.append(node)
for nxt, _ in graph[node]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0: queue.append(nxt)
# Relax in topological order
dist = [float('inf')] * V
dist[source] = 0
for u in topo:
if dist[u] != float('inf'):
for v, w in graph[u]:
dist[v] = min(dist[v], dist[u] + w)
return distShortest Path in a Matrix with Obstacles
A common interview variant: find the shortest path in a 2D grid from top-left to bottom-right where cells can be blocked. This is an unweighted BFS problem (each step costs 1). Use BFS with 4-directional movement, marking cells as visited when enqueued (not when dequeued) to avoid revisiting. If obstacles can be passed through (with cost), use Dijkstra on the 2D grid treating it as a weighted graph.
from collections import deque
def shortest_path_binary_matrix(grid):
n = len(grid)
if grid[0][0] == 1 or grid[n-1][n-1] == 1:
return -1
queue = deque([(0, 0, 1)]) # (row, col, distance)
visited = {(0, 0)}
dirs = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]
while queue:
r, c, d = queue.popleft()
if r == n-1 and c == n-1:
return d
for dr, dc in dirs:
nr, nc = r+dr, c+dc
if 0<=nr<n and 0<=nc<n and grid[nr][nc]==0 and (nr,nc) not in visited:
visited.add((nr,nc))
queue.append((nr, nc, d+1))
return -1
print(shortest_path_binary_matrix([[0,0,0],[1,1,0],[1,1,0]])) # 4Multiple-Source BFS
When multiple starting points exist (e.g., multiple 'gates' in a grid, multiple origins in a map), run multi-source BFS: enqueue all sources with distance 0 simultaneously. This computes the shortest distance from the nearest source to every cell in one BFS pass. This technique avoids running BFS from each source separately and is O(V+E) total.
Recap of Algorithm Selection
A concise decision tree: single source, non-negative weights → Dijkstra O((V+E) log V). Single source, negative weights → Bellman-Ford O(VE). All pairs, small V → Floyd-Warshall O(V³). DAG, any weights → Topological Sort + Relax O(V+E). Unweighted → BFS O(V+E). Grid paths → BFS (unweighted) or Dijkstra with heap (weighted). Memorise this table — it answers follow-up questions in any shortest-path interview.
Path Finding in Interview Questions
Many interview problems ask for the actual path, not just the cost. Always clarify: do you need the path or just the distance? If the path is needed, allocate a prev dict from the start. Common mistakes: forgetting to initialise prev[source] = None as a terminal condition, and confusing the reconstruction order (trace back from destination to source, then reverse). Practice reconstructing paths on 3-4 node examples before applying to larger problems.
Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: Network Delay Time is answered by max(dist.values()) after Dijkstra, path reconstruction uses a prev array updated whenever dist[v] improves, and bidirectional BFS can halve the search space for single-pair unweighted shortest paths. Next up we enter graph ordering with Kahn's Algorithm for topological sort.
Frequently asked questions
Is the “Network Delay Time and Path Reconstruction” lesson free?
Yes — the full text of “Network Delay Time and Path Reconstruction” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Network Delay Time and Path Reconstruction”?
Solve network-delay-time with Dijkstra, reconstruct the actual shortest path using a predecessor map, and discuss bidirectional BFS for large graphs. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 4 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Network Delay Time and Path Reconstruction” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Dijkstra's Algorithm with a Priority Queue
- Bellman-Ford and Negative Cycles
- Floyd-Warshall: All-Pairs Shortest Paths
- Network Delay Time and Path Reconstruction