AI Hints
Home›DSA in Python Tutorial›Weighted Graphs
DSA in Python · Lesson 83 of 132

Dijkstra's Algorithm

Shortest routes with a heap.

⏱ 2 min read▶ Video at 1:38:18🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

Dijkstra's algorithm is one of the most famous algorithms ever written. Map apps, network routers, and games all use versions of it. And in Python, with a heap, it's only about a dozen lines.

Dijkstra's Algorithm
From the video: Dijkstra's Algorithm
  • One of the most famous algorithms
  • Maps, routers, games
  • About a dozen lines

Dijkstra in code

The heap holds pairs of distance and place, so heap pop always gives the nearest unexplored place. If we've already found a shorter way to it, we skip it. Otherwise, for each neighbour, we work out the distance through this place. If it beats the best known distance, we record it, and push it onto the heap. Run it. The library is only seven minutes away, through the park, the shop, and the school.

dijkstra.pypython
import heapq
from roads import roads

def dijkstra(start):
    best = {start: 0}
    heap = [(0, start)]
    while heap:
        dist, place = heapq.heappop(heap)
        if dist > best[place]:
            continue
        for nxt, w in roads[place].items():
            new = dist + w
            if new < best.get(nxt, float("inf")):
                best[nxt] = new
                heapq.heappush(heap, (new, nxt))
    return best

print(dijkstra("Home"))
Output
{'Home': 0, 'Shop': 3, 'Park': 1, 'School': 6, 'Library': 7}
Also uses roads.py
roads = {
    "Home":    {"Shop": 4, "Park": 1},
    "Park":    {"Shop": 2, "School": 6},
    "Shop":    {"School": 3, "Library": 7},
    "School":  {"Library": 1},
    "Library": {},
}

Dijkstra facts

With a heap, Dijkstra runs in O of E log V. It needs every weight to be zero or more. With negative weights, it can give wrong answers, and you'd use a different algorithm, called Bellman Ford. To get the route itself, not just the distance, record each place's parent, just like we did with breadth first search.

keyvalue
CostO(E log V)
Needsno negative weights
Negative weightsBellman-Ford
The routerecord parents

Summary

Dijkstra's algorithm uses a heap to always settle the nearest place next. It finds the shortest distances to every place. Next, putting tasks in the right order.

Key takeaways
  • Heap of (distance, place)
  • Relax each edge
  • O(E log V)
Next up: Topological Sort — what must come first