Implementing Dijkstra's shortest path algorithm

The algorithm

1. Give every vertex a distance of infinity, except the start, which gets 0. Mark every vertex unvisited.

2. Choose the unvisited vertex with the smallest current distance. Its distance is now final; mark it visited.

3. For each neighbour, calculate distance to current + edge weight. If that is less than the neighbour's recorded distance, update it and record current as the neighbour's previous vertex.

4. Repeat steps 2 and 3 until every vertex is visited (or the smallest remaining distance is infinity, meaning the rest are unreachable).

5. Follow the previous vertices back from the target to recover the path.

It is a greedy algorithm: it always settles the closest unsettled vertex next. This is only correct when no edge weight is negative.

Python implementation

The graph is an adjacency list stored as a dictionary of dictionaries (see the graphs lesson). float("inf") represents infinity. min(unvisited, key=...) picks the closest unvisited vertex.

def dijkstra(graph, start):
    distances = {v: float("inf") for v in graph}
    previous = {v: None for v in graph}
    distances[start] = 0
    unvisited = list(graph)
    while unvisited:
        current = min(unvisited, key=lambda v: distances[v])
        if distances[current] == float("inf"):
            break                                   # the rest cannot be reached
        unvisited.remove(current)
        for neighbour, weight in graph[current].items():
            new_distance = distances[current] + weight
            if new_distance < distances[neighbour]:
                distances[neighbour] = new_distance
                previous[neighbour] = current
    return distances, previous

def path_to(previous, target):
    path = []
    while target is not None:
        path.insert(0, target)
        target = previous[target]
    return path

Using it

This graph is used in the questions too:

graph = {
    "A": {"B": 4, "C": 1},
    "B": {"A": 4, "C": 2, "D": 5},
    "C": {"A": 1, "B": 2, "D": 8, "E": 10},
    "D": {"B": 5, "C": 8, "E": 2, "F": 6},
    "E": {"C": 10, "D": 2, "F": 3},
    "F": {"D": 6, "E": 3},
}

dist, prev = dijkstra(graph, "A")
print(dist)
print(path_to(prev, "F"), dist["F"])

Output:

{'A': 0, 'B': 3, 'C': 1, 'D': 8, 'E': 10, 'F': 13}
['A', 'C', 'B', 'D', 'E', 'F'] 13

The vertices are settled in the order A, C, B, D, E, F. For large graphs, a priority queue (the heapq module) finds the closest vertex faster than min(), but min() is clear and correct.

Worked example

Using the lesson's graph, explain how the distance to B changes during the algorithm.

1. Start: A = 0, everything else infinity.
2. Settle A: B becomes 0 + 4 = 4 (previous A); C becomes 0 + 1 = 1.
3. Settle C (distance 1, the smallest): via C, B would be 1 + 2 = 3, which is less than 4, so B becomes 3 with previous C.
4. Settle B (3): no later update can beat it. Final distance to B: 3.

Answer: B's first estimate of 4 is improved to 3 by going through C, and the previous vertex changes to C.

Check yourself

1. Using the lesson's dijkstra function and graph, what does this print? ```python def dijkstra(graph, start): distances = {v: float("inf") for v in graph} previous = {v: None for v in graph} distances[start] = 0 unvisited = list(graph) while unvisited: current = min(unvisited, key=lambda v: distances[v]) if distances[current] == float("inf"): break # the rest cannot be reached unvisited.remove(current) for neighbour, weight in graph[current].items(): new_distance = distances[current] + weight if new_distance < distances[neighbour]: distances[neighbour] = new_distance previous[neighbour] = current return distances, previous def path_to(previous, target): path = [] while target is not None: path.insert(0, target) target = previous[target] return path graph = { "A": {"B": 4, "C": 1}, "B": {"A": 4, "C": 2, "D": 5}, "C": {"A": 1, "B": 2, "D": 8, "E": 10}, "D": {"B": 5, "C": 8, "E": 2, "F": 6}, "E": {"C": 10, "D": 2, "F": 3}, "F": {"D": 6, "E": 3}, } print(dijkstra(graph, "A")[0]["E"]) ```
   Show answer

   10. Shortest route A, C, B, D, E: 1 + 2 + 5 + 2 = `10`. The direct C to E edge (10) gives 11, which is longer.

2. Using the lesson's functions and graph, what does this print? ```python def dijkstra(graph, start): distances = {v: float("inf") for v in graph} previous = {v: None for v in graph} distances[start] = 0 unvisited = list(graph) while unvisited: current = min(unvisited, key=lambda v: distances[v]) if distances[current] == float("inf"): break # the rest cannot be reached unvisited.remove(current) for neighbour, weight in graph[current].items(): new_distance = distances[current] + weight if new_distance < distances[neighbour]: distances[neighbour] = new_distance previous[neighbour] = current return distances, previous def path_to(previous, target): path = [] while target is not None: path.insert(0, target) target = previous[target] return path graph = { "A": {"B": 4, "C": 1}, "B": {"A": 4, "C": 2, "D": 5}, "C": {"A": 1, "B": 2, "D": 8, "E": 10}, "D": {"B": 5, "C": 8, "E": 2, "F": 6}, "E": {"C": 10, "D": 2, "F": 3}, "F": {"D": 6, "E": 3}, } dist, prev = dijkstra(graph, "A") print(path_to(prev, "D")) ```
   Show answer

   ['A', 'C', 'B', 'D']. D is reached most cheaply through C and B: 1 + 2 + 5 = 8, beating C to D directly (1 + 8 = 9). Output: `['A', 'C', 'B', 'D']`

3. Using the lesson's dijkstra function and graph, what does this print? ```python def dijkstra(graph, start): distances = {v: float("inf") for v in graph} previous = {v: None for v in graph} distances[start] = 0 unvisited = list(graph) while unvisited: current = min(unvisited, key=lambda v: distances[v]) if distances[current] == float("inf"): break # the rest cannot be reached unvisited.remove(current) for neighbour, weight in graph[current].items(): new_distance = distances[current] + weight if new_distance < distances[neighbour]: distances[neighbour] = new_distance previous[neighbour] = current return distances, previous def path_to(previous, target): path = [] while target is not None: path.insert(0, target) target = previous[target] return path graph = { "A": {"B": 4, "C": 1}, "B": {"A": 4, "C": 2, "D": 5}, "C": {"A": 1, "B": 2, "D": 8, "E": 10}, "D": {"B": 5, "C": 8, "E": 2, "F": 6}, "E": {"C": 10, "D": 2, "F": 3}, "F": {"D": 6, "E": 3}, } print(dijkstra(graph, "F")[0]["A"]) ```
   Show answer

   13. The graph is undirected, so the shortest distance from F to A equals A to F: `13`.

4. This version records the order in which vertices are settled on the lesson's graph. What does it print? ```python def dijkstra(graph, start): distances = {v: float("inf") for v in graph} previous = {v: None for v in graph} distances[start] = 0 unvisited = list(graph) while unvisited: current = min(unvisited, key=lambda v: distances[v]) if distances[current] == float("inf"): break # the rest cannot be reached unvisited.remove(current) order.append(current) for neighbour, weight in graph[current].items(): new_distance = distances[current] + weight if new_distance < distances[neighbour]: distances[neighbour] = new_distance previous[neighbour] = current return distances, previous def path_to(previous, target): path = [] while target is not None: path.insert(0, target) target = previous[target] return path graph = { "A": {"B": 4, "C": 1}, "B": {"A": 4, "C": 2, "D": 5}, "C": {"A": 1, "B": 2, "D": 8, "E": 10}, "D": {"B": 5, "C": 8, "E": 2, "F": 6}, "E": {"C": 10, "D": 2, "F": 3}, "F": {"D": 6, "E": 3}, } order = [] dijkstra(graph, "A") print(order) ```
   Show answer

   ['A', 'C', 'B', 'D', 'E', 'F']. Vertices are settled in increasing order of final distance: A 0, C 1, B 3, D 8, E 10, F 13. Output: `['A', 'C', 'B', 'D', 'E', 'F']`

5. Using the lesson's dijkstra function, what does this print? ```python def dijkstra(graph, start): distances = {v: float("inf") for v in graph} previous = {v: None for v in graph} distances[start] = 0 unvisited = list(graph) while unvisited: current = min(unvisited, key=lambda v: distances[v]) if distances[current] == float("inf"): break # the rest cannot be reached unvisited.remove(current) for neighbour, weight in graph[current].items(): new_distance = distances[current] + weight if new_distance < distances[neighbour]: distances[neighbour] = new_distance previous[neighbour] = current return distances, previous def path_to(previous, target): path = [] while target is not None: path.insert(0, target) target = previous[target] return path g = {"P": {"Q": 2}, "Q": {"P": 2}, "R": {}} d, _ = dijkstra(g, "P") print(d["Q"], d["R"]) ```
   Show answer

   2 inf. R has no edges, so its distance stays infinity and the loop breaks when only R is left. Output: `2 inf`

6. Why must the graph have no negative edge weights for Dijkstra's algorithm?
   • Python cannot store negative numbers in dictionaries
   • Once a vertex is settled its distance is assumed final, but a later negative edge could make a shorter route
   • Negative weights make the graph directed
   • The algorithm would run forever
   Show answer

   Once a vertex is settled its distance is assumed final, but a later negative edge could make a shorter route. The greedy choice is only safe if adding more edges can never reduce a distance.

7. What is the purpose of the previous dictionary in the implementation?
   • It stores the distances
   • It stores the unvisited vertices
   • It prevents negative weights
   • It records how each vertex was reached, so the shortest path can be reconstructed
   Show answer

   It records how each vertex was reached, so the shortest path can be reconstructed. Following previous links back from the target gives the route in reverse.

8. At each step, which vertex does Dijkstra's algorithm settle next?
   • The neighbour with the smallest edge weight from the start
   • The vertex with the most edges
   • The unvisited vertex with the smallest current distance
   • The next vertex in alphabetical order
   Show answer

   The unvisited vertex with the smallest current distance. Choosing the smallest tentative distance is the greedy step that makes the algorithm correct.

Practise with instant feedback Print this lesson

Sources

• Pearson Edexcel International Advanced Subsidiary/Advanced Level in Computer Science specification, Issue 1 (March 2026)
• Pearson Edexcel IAL Computer Science Unit 4 Programming Language Subset (PLS)
• Pearson Edexcel IAL Computer Science sample assessment materials (Unit 3 and Unit 4)

Last updated 8 November 2026. Spotted a mistake? Tell us.