DSA course menu
Dijkstra's Algorithm in Python: Shortest Paths in Weighted Graphs
Learn Dijkstra's shortest path algorithm with a priority queue: how it works step by step, rebuilding the path, its O((V + E) log V) cost, why negative weights break it, and the Bellman-Ford alternative.
On this page
BFS finds the path with the fewest edges. When edges have weights (distances, travel times, costs), the cheapest path may use more edges. Dijkstra's algorithm finds the cheapest path from one start vertex to every other vertex, as long as no weight is negative.
The idea#
Keep a tentative distance for every vertex: 0 for the start, infinity for the rest. Then repeat:
- Pick the unfinished vertex with the smallest tentative distance. Its distance is now final.
- Relax its edges: for each neighbour, if going through this vertex is cheaper than the neighbour's current distance, update it.
Picking "the smallest" quickly is exactly what a heap is for.
The algorithm#
import heapq
graph = {
"A": [("B", 4), ("C", 2)],
"B": [("C", 5), ("D", 10)],
"C": [("E", 3)],
"D": [("F", 11)],
"E": [("D", 4)],
"F": [],
}
def dijkstra(graph, start):
dist = {v: float("inf") for v in graph}
dist[start] = 0
heap = [(0, start)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]:
continue # an old, longer entry: skip it
for v, weight in graph[u]:
new = d + weight
if new < dist[v]:
dist[v] = new
heapq.heappush(heap, (new, v))
return dist
print(dijkstra(graph, "A")){'A': 0, 'B': 4, 'C': 2, 'D': 9, 'E': 5, 'F': 20}The direct edge B → D costs 10, but A → C → E → D costs 2 + 3 + 4 = 9, so D's distance is 9.
Instead of updating an entry inside the heap, the code pushes a new entry and skips stale ones when they are popped (d > dist[u]). That is the standard way to use Python's heapq.
Rebuilding the route#
Store each vertex's predecessor whenever its distance improves, then walk back from the target:
import heapq
graph = {
"A": [("B", 4), ("C", 2)],
"B": [("C", 5), ("D", 10)],
"C": [("E", 3)],
"D": [("F", 11)],
"E": [("D", 4)],
"F": [],
}
def shortest_route(graph, start, goal):
dist = {v: float("inf") for v in graph}
prev = {}
dist[start] = 0
heap = [(0, start)]
while heap:
d, u = heapq.heappop(heap)
if u == goal:
break
if d > dist[u]:
continue
for v, w in graph[u]:
if d + w < dist[v]:
dist[v] = d + w
prev[v] = u
heapq.heappush(heap, (d + w, v))
if dist[goal] == float("inf"):
return None
path = [goal]
while path[-1] != start:
path.append(prev[path[-1]])
return path[::-1], dist[goal]
print(shortest_route(graph, "A", "F"))(['A', 'C', 'E', 'D', 'F'], 20)Stopping as soon as the goal is popped is safe: once a vertex leaves the heap, its distance is final.
Cost#
Each edge may push one heap entry, and each push or pop costs O(log V). The total is O((V + E) log V). For road maps with millions of junctions that is fast; a version without a heap (scanning for the minimum each time) would be O(V²).
Why negative weights break it#
Dijkstra assumes that once a vertex has the smallest distance, no later path can make it cheaper. A negative edge can:
import heapq
graph = {"S": [("A", 2), ("B", 5)], "A": [], "B": [("A", -4)]}
def dijkstra(graph, start):
dist = {v: float("inf") for v in graph}
dist[start] = 0
done = set()
heap = [(0, start)]
while heap:
d, u = heapq.heappop(heap)
if u in done:
continue
done.add(u) # Dijkstra treats u as final here
for v, w in graph[u]:
if v not in done and d + w < dist[v]:
dist[v] = d + w
heapq.heappush(heap, (d + w, v))
return dist
print(dijkstra(graph, "S")){'S': 0, 'A': 2, 'B': 5}The true shortest distance to A is S → B → A = 5 − 4 = 1, but Dijkstra already finalised A at 2. With negative weights, use Bellman-Ford.
Bellman-Ford#
Bellman-Ford relaxes every edge, V − 1 times. That is enough for any shortest path (which has at most V − 1 edges). One more round that still improves something means a negative cycle: a loop you could go around forever to make paths ever cheaper.
def bellman_ford(vertices, edges, start):
dist = {v: float("inf") for v in vertices}
dist[start] = 0
for _ in range(len(vertices) - 1):
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
for u, v, w in edges:
if dist[u] + w < dist[v]:
return None # negative cycle
return dist
print(bellman_ford(["S", "A", "B"], [("S", "A", 2), ("S", "B", 5), ("B", "A", -4)], "S"))
print(bellman_ford(["X", "Y"], [("X", "Y", 1), ("Y", "X", -3)], "X")){'S': 0, 'A': 1, 'B': 5}
NoneBellman-Ford costs O(V · E): slower, but correct with negative edges.
Common mistakes#
Practice#
Practice exercise
Network delay: signals travel along directed, weighted links between n servers (numbered 1 to n). Starting from server k, how long until every server has received the signal? Return -1 if some server is never reached.
Show hint
Run Dijkstra from k. The answer is the largest of all the shortest distances, unless one is infinity.
Show solution
import heapq
def network_delay(times, n, k):
graph = {i: [] for i in range(1, n + 1)}
for u, v, w in times:
graph[u].append((v, w))
dist = {i: float("inf") for i in graph}
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 d + w < dist[v]:
dist[v] = d + w
heapq.heappush(heap, (d + w, v))
longest = max(dist.values())
return -1 if longest == float("inf") else longest
print(network_delay([(2, 1, 1), (2, 3, 1), (3, 4, 1)], 4, 2))
print(network_delay([(1, 2, 1)], 2, 2))2
-1Key takeaway#
Next: finding one route faster with a good guess, in A* Pathfinding.
Finished this lesson?