Dijkstra's Algorithm
Dijkstra's algorithm finds the shortest path from one node to all others in a weighted graph. It's BFS's smarter cousin - instead of exploring level by level, it always explores the closest unvisited node first.
The Core Idea
Maintain distances to all nodes (initially infinite except source). Repeatedly pick the unvisited node with the smallest distance, mark it visited, and update its neighbors' distances if you found a shorter path through this node.
Dijkstra is greedy and it works because edge weights are non-negative. Once you've found the shortest path to a node, you'll never find a shorter one. Negative edges break this guarantee.
Classic Implementation
import heapq
def dijkstra(graph, start):
distances = {node: float('inf') for node in graph}
distances[start] = 0
heap = [(0, start)] # (distance, node)
while heap:
dist, node = heapq.heappop(heap)
# Skip if we've found a better path
if dist > distances[node]:
continue
for neighbor, weight in graph[node]:
new_dist = dist + weight
if new_dist < distances[neighbor]:
distances[neighbor] = new_dist
heapq.heappush(heap, (new_dist, neighbor))
return distancesClassic: Network Delay Time
How long until all nodes receive a signal?
def networkDelayTime(times, n, k):
# Build adjacency list
graph = {i: [] for i in range(1, n + 1)}
for u, v, w in times:
graph[u].append((v, w))
distances = dijkstra(graph, k)
max_dist = max(distances.values())
return max_dist if max_dist < float('inf') else -1When to Use Dijkstra
- Shortest path - In weighted graphs with non-negative edges
- Network routing - Find optimal paths
- GPS navigation - Real-world shortest paths
- Game AI pathfinding - With varying terrain costs
Dijkstra doesn't work with negative edge weights. Use Bellman-Ford instead, which is slower but handles negatives. For negative cycles, there's no shortest path at all.