Dijkstra's Algorithm
An algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks.
Visualization
Details
Analogy
Think of it like finding the fastest route on a GPS. The algorithm starts at your location. It explores the nearest intersections first. It keeps track of the 'shortest known time' to reach every intersection. As it discovers a new, quicker path to an intersection it already knew about, it updates its records. It continues spreading out, always prioritizing the overall closest intersection, until it has found the fastest route to your destination.
Purpose
To find the shortest path from a single source node to all other nodes in a weighted graph with non-negative edge weights.
Use Cases
Network routing protocols, GPS systems for finding the shortest path, flight planning, and link-state routing protocols.
Algorithm Steps
initialize distances[all] = infinity
distances[start] = 0
create priority queue Q
add start to Q
while Q is not empty:
u = vertex with min distance in Q
remove u from Q
for each neighbor v of u:
alt = distances[u] + weight(u, v)
if alt < distances[v]:
distances[v] = alt
add v to Q
Explanation
What's Happening?
Start at node A. Distances: {B: 4, C: 2}. The next closest node is C.
Code Implementation
import heapq
def dijkstra(graph, start_node):
distances = {node: float('infinity') for node in graph}
distances[start_node] = 0
priority_queue = [(0, start_node)]
previous_nodes = {node: None for node in graph}
while priority_queue:
current_distance, current_node = heapq.heappop(priority_queue)
if current_distance > distances[current_node]:
continue
for neighbor, weight in graph[current_node].items():
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
previous_nodes[neighbor] = current_node
heapq.heappush(priority_queue, (distance, neighbor))
return distances, previous_nodes