Dijkstra's Algorithm — Shortest Path on a Weighted Graph

Build the mental model

BFS finds shortest paths by counting edges, implicitly assuming every edge costs the same one 'step.' Once edges carry different weights — one lesson-to-lesson transition takes 5 minutes, another takes 30 — that assumption breaks: a path with more hops can legitimately be cheaper than one with fewer. Dijkstra's algorithm generalizes BFS for this case using a min-heap priority queue instead of a plain queue. It maintains the current known-shortest distance to every node (starting at infinity, except 0 for the start), and repeatedly pops the node with the smallest known distance from the heap — the greedy insight is that once popped, that node's distance is final, because any other path to it would have to go through a node with an equal or larger distance, which can't produce something smaller. It then relaxes each neighbor: if reaching the neighbor through the current node beats its previously known distance, update it and push the new distance onto the heap. This greedy 'always expand the cheapest frontier node' strategy fails outright with negative edge weights, because a negative edge could later undercut a distance already treated as final — Bellman-Ford exists specifically to handle that case, at higher cost.

Connect it to a real scenario

The Tutorial Platform can model each lesson-to-lesson transition with a weight — say, estimated minutes to complete the next lesson, or a difficulty jump penalty — turning 'find the best learning path from a learner's current level to a goal lesson' into a shortest-path problem where fewer hops isn't automatically better. Dijkstra's algorithm over that weighted lesson graph finds the path minimizing total estimated time or difficulty-adjusted cost, not just edge count, which is what BFS alone could offer. This is the natural upgrade from the plain BFS-based related-lessons traversal once the platform wants to optimize for something more meaningful than hop count, like total study time to reach a goal.

• BFS assumes every edge has equal weight — once weights differ, you need Dijkstra.
• Dijkstra uses a min-heap priority queue to always expand the node with the currently-cheapest known distance next.
• Dijkstra fails with negative edge weights — Bellman-Ford exists to handle that case instead.

Try the working example

import heapq

# weighted adjacency list: lesson -> [(neighbor, minutes_to_complete), ...]
graph = {
    "start": [("basics", 5), ("loops", 9)],
    "basics": [("loops", 2), ("functions", 6)],
    "loops": [("functions", 1), ("goal", 8)],
    "functions": [("goal", 3)],
    "goal": [],
}

def dijkstra(graph, start):
    distances = {node: float("inf") for node in graph}
    distances[start] = 0
    pq = [(0, start)]  # (distance, node)
    while pq:
        dist, node = heapq.heappop(pq)
        if dist > distances[node]:
            continue  # stale entry, a shorter path was already found
        for neighbor, weight in graph[node]:
            new_dist = dist + weight
            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                heapq.heappush(pq, (new_dist, neighbor))
    return distances

print(dijkstra(graph, "start"))

Prints {'start': 0, 'basics': 5, 'loops': 7, 'functions': 8, 'goal': 11} — the shortest distance from start to every node.

Wikipedia — Dijkstra's algorithm — Data Structures & Algorithms