Solution: Dijkstra's Algorithm Implementation
import heapq
from collections import defaultdict
def dijkstra(graph, start, num_nodes):
"""
Find shortest paths from start to all nodes
Args:
graph: Adjacency list {node: [(neighbor, weight), ...]}
start: Starting node
num_nodes: Total number of nodes
Returns:
Dictionary {node: shortest_distance_from_start}
Time: O((V + E) log V) with binary heap
Space: O(V)
"""
# Initialize distances
distances = {i: float('inf') for i in range(num_nodes)}
distances[start] = 0
# Min heap: (distance, node)
min_heap = [(0, start)]
visited = set()
while min_heap:
current_dist, node = heapq.heappop(min_heap)
# Skip if already visited
if node in visited:
continue
visited.add(node)
# Explore neighbors
for neighbor, weight in graph.get(node, []):
if neighbor in visited:
continue
new_dist = current_dist + weight
# Relaxation: update if found shorter path
if new_dist < distances[neighbor]:
distances[neighbor] = new_dist
heapq.heappush(min_heap, (new_dist, neighbor))
return distances
# Example usage
graph = {
0: [(1, 4), (2, 1)],
1: [(3, 1)],
2: [(1, 2), (3, 5)],
3: []
}
distances = dijkstra(graph, start=0, num_nodes=4)
print(distances) # {0: 0, 1: 3, 2: 1, 3: 4}
Complete Example: Network Delay Time
def networkDelayTime(times, n, k):
"""
LeetCode 743: Network Delay Time
You are given a network of n nodes labeled 1 to n.
times[i] = [u, v, w] means signal takes w time to travel from u to v.
Return minimum time for all nodes to receive signal from node k.
If impossible, return -1.
Example:
Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2
"""
# Build adjacency list
graph = defaultdict(list)
for u, v, w in times:
graph[u].append((v, w))
# Dijkstra's
distances = {i: float('inf') for i in range(1, n + 1)}
distances[k] = 0
min_heap = [(0, k)]
visited = set()
while min_heap:
time, node = heapq.heappop(min_heap)
if node in visited:
continue
visited.add(node)
for neighbor, weight in graph[node]:
new_time = time + weight
if new_time < distances[neighbor]:
distances[neighbor] = new_time
heapq.heappush(min_heap, (new_time, neighbor))
# Check if all nodes reachable
max_time = max(distances.values())
return max_time if max_time != float('inf') else -1
# Test
print(networkDelayTime([[2,1,1],[2,3,1],[3,4,1]], 4, 2)) # 2
Path Reconstruction
def dijkstra_with_path(graph, start, end, num_nodes):
"""
Find shortest path and reconstruct the actual path
Returns:
(distance, path) tuple
"""
distances = {i: float('inf') for i in range(num_nodes)}
distances[start] = 0
parent = {i: None for i in range(num_nodes)}
min_heap = [(0, start)]
visited = set()
while min_heap:
current_dist, node = heapq.heappop(min_heap)
if node == end:
break
if node in visited:
continue
visited.add(node)
for neighbor, weight in graph.get(node, []):
new_dist = current_dist + weight
if new_dist < distances[neighbor]:
distances[neighbor] = new_dist
parent[neighbor] = node
heapq.heappush(min_heap, (new_dist, neighbor))
# Reconstruct path
if distances[end] == float('inf'):
return (float('inf'), [])
path = []
current = end
while current is not None:
path.append(current)
current = parent[current]
return (distances[end], path[::-1])
# Test
graph = {
0: [(1, 4), (2, 1)],
1: [(3, 1)],
2: [(1, 2), (3, 5)],
3: []
}
dist, path = dijkstra_with_path(graph, 0, 3, 4)
print(f"Distance: {dist}, Path: {path}") # Distance: 4, Path: [0, 2, 1, 3]
Modified Dijkstra's: Path With Minimum Effort
def minimumEffortPath(heights):
"""
LeetCode 1631: Path With Minimum Effort
Find path from top-left to bottom-right that minimizes maximum
absolute difference in heights between consecutive cells.
This is Dijkstra's where "distance" is max effort so far.
"""
rows, cols = len(heights), len(heights[0])
efforts = [[float('inf')] * cols for _ in range(rows)]
efforts[0][0] = 0
min_heap = [(0, 0, 0)] # (effort, row, col)
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
while min_heap:
effort, r, c = heapq.heappop(min_heap)
if r == rows - 1 and c == cols - 1:
return effort
if effort > efforts[r][c]:
continue
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols:
new_effort = max(effort, abs(heights[nr][nc] - heights[r][c]))
if new_effort < efforts[nr][nc]:
efforts[nr][nc] = new_effort
heapq.heappush(min_heap, (new_effort, nr, nc))
return 0
Complexity Analysis
Time Complexity:
- Each vertex extracted from heap once: O(V log V)
- Each edge relaxed once: O(E log V)
- Total: O((V + E) log V)
Space Complexity:
- Distances array: O(V)
- Min heap: O(V)
- Visited set: O(V)
- Total: O(V)
Common Mistakes
- Forgetting to check if node already visited (leads to duplicates in heap)
- Using with negative weights (Dijkstra's doesn't work!)
- Not using visited set (heap may contain duplicate nodes)
- Incorrect heap priority (should be distance, not node ID)
When NOT to Use Dijkstra's
- Negative weights: Use Bellman-Ford instead
- All-pairs shortest path: Use Floyd-Warshall
- Unweighted graph: Simple BFS is faster
- Negative cycles: No algorithm works (infinite loop)
Related Problems
