DSA Shortest Path
Dijkstra's algorithm finds the shortest-weight path from a source vertex to every other vertex in a graph whose edge weights are all non-negative.
The Shortest Path Problem
In a weighted graph, the shortest path between two vertices is the path whose edge weights sum to the smallest total, which is not necessarily the path with the fewest edges. Shortest-path algorithms apply anywhere a 'cost' needs minimizing: driving distance, network latency, currency conversion fees, or flight prices.
Dijkstra's Algorithm
Dijkstra's algorithm is a greedy algorithm that finds the shortest path from a single source vertex to every other vertex. It keeps a running 'best known distance' for every vertex, starting at 0 for the source and infinity for everything else, and repeatedly selects the unvisited vertex with the smallest known distance, then relaxes (updates) the distances of its neighbors. Critically, Dijkstra's algorithm only produces correct results when every edge weight is non-negative.
Example 1: Dijkstra's Algorithm with a Priority Queue
import heapq
def dijkstra(graph, start):
distances = {vertex: float("inf") for vertex in graph}
distances[start] = 0
priority_queue = [(0, start)] # (distance, vertex)
while priority_queue:
current_distance, current_vertex = heapq.heappop(priority_queue)
if current_distance > distances[current_vertex]:
continue # a shorter path was already found; skip this stale entry
for neighbor, weight in graph[current_vertex]:
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(priority_queue, (distance, neighbor))
return distances
graph = {
"A": [("B", 4), ("C", 1)],
"B": [("A", 4), ("D", 1)],
"C": [("A", 1), ("B", 2), ("D", 5)],
"D": [("B", 1), ("C", 5)],
}
print(dijkstra(graph, "A")) # {'A': 0, 'B': 3, 'C': 1, 'D': 4}
Why Dijkstra Requires Non-Negative Weights
The algorithm's greedy step assumes that once a vertex is popped from the priority queue with its final shortest distance, no later discovery can ever produce a shorter path to it, because every remaining edge can only add a non-negative amount of weight. A negative edge weight breaks that assumption: a longer-looking path could later subtract distance and beat a path already treated as final, producing an incorrect result. Graphs with negative edges, but no negative-weight cycle, need the Bellman-Ford algorithm instead, which trades speed for the ability to relax every edge repeatedly.
- Set the distance to the source vertex to 0 and every other vertex to infinity.
- Add the source vertex to a min-priority queue keyed by distance.
- Repeatedly pop the vertex with the smallest known distance from the queue.
- Relax each outgoing edge: if going through the current vertex gives a shorter distance to a neighbor, update it and push the neighbor back onto the queue.
- Stop when the queue is empty; every reachable vertex now holds its shortest distance from the source.
Example 2: Reconstructing the Shortest Path
import heapq
def dijkstra_with_path(graph, start):
distances = {vertex: float("inf") for vertex in graph}
distances[start] = 0
predecessors = {vertex: None for vertex in graph}
priority_queue = [(0, start)]
while priority_queue:
current_distance, current_vertex = heapq.heappop(priority_queue)
if current_distance > distances[current_vertex]:
continue
for neighbor, weight in graph[current_vertex]:
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
predecessors[neighbor] = current_vertex
heapq.heappush(priority_queue, (distance, neighbor))
return distances, predecessors
def build_path(predecessors, start, target):
path = [target]
while path[-1] != start:
path.append(predecessors[path[-1]])
path.reverse()
return path
graph = {
"A": [("B", 4), ("C", 1)],
"B": [("A", 4), ("D", 1)],
"C": [("A", 1), ("B", 2), ("D", 5)],
"D": [("B", 1), ("C", 5)],
}
distances, predecessors = dijkstra_with_path(graph, "A")
print(build_path(predecessors, "A", "D")) # ['A', 'C', 'B', 'D']
Example 3: Shortest Distances Across a City Network
cities = {
"Denver": [("Omaha", 8), ("Wichita", 6)],
"Omaha": [("Denver", 8), ("Chicago", 5)],
"Wichita": [("Denver", 6), ("Chicago", 9)],
"Chicago": [("Omaha", 5), ("Wichita", 9)],
}
shortest_distances = dijkstra(cities, "Denver")
for city, distance in shortest_distances.items():
print(f"Denver -> {city}: {distance}")
# Denver -> Denver: 0
# Denver -> Omaha: 8
# Denver -> Wichita: 6
# Denver -> Chicago: 13
Exercise: DSA Shortest Path
What limitation does Dijkstra's algorithm have regarding edge weights?
