Dijkstra's shortest path algorithm

The algorithm

1. Set the distance to the start vertex to 0 and every other vertex to infinity. All vertices are unvisited.

2. Choose the unvisited vertex with the smallest distance and mark it visited (its distance is now final).

3. For each unvisited neighbour, calculate distance via the current vertex = current distance + edge weight. If this is smaller than the neighbour's recorded distance, update it and record the current vertex as its previous vertex.

4. Repeat steps 2 and 3 until every vertex is visited (or the target is visited).

5. Read the path backwards from the target using the previous vertices.

It is a greedy algorithm: it always settles the closest unvisited vertex.

Trace

Edges: A-B 4, A-C 2, B-C 1, B-D 5, C-D 8, C-E 10, D-E 2, D-F 6, E-F 3 (undirected). Start A.

Shortest A to F = 13, path A -> C -> B -> D -> E -> F

Code outline

import heapq
def dijkstra(graph, start):
    dist = {v: float("inf") for v in graph}
    prev = {v: None for v in graph}
    dist[start] = 0
    queue = [(0, start)]
    visited = set()
    while queue:
        d, v = heapq.heappop(queue)        # closest unvisited vertex
        if v in visited:
            continue
        visited.add(v)
        for w, weight in graph[v].items():
            if d + weight < dist[w]:
                dist[w] = d + weight
                prev[w] = v
                heapq.heappush(queue, (dist[w], w))
    return dist, prev

Strengths and limits

Strengths: always finds the shortest path when weights are not negative; gives shortest distances to every vertex in one run.

Limits: explores in all directions, so it can examine many vertices that lead away from the target (A* fixes this); does not work with negative edge weights; with a simple list it is O(V²), improved with a priority queue.

Worked example

Use the table to find the shortest route from A to F.

1. Final distances: A 0, B 3, C 2, D 8, E 10, F 13.
2. Work back from F: F came from E, E from D, D from B, B from C, C from A.

Answer: A -> C -> B -> D -> E -> F, length 13

Check yourself

1. In the trace graph, what is the shortest distance from A to F?
   Show answer

   13. A-C-B-D-E-F = 2 + 1 + 5 + 2 + 3 = 13.

2. In the trace graph, what is the shortest distance from A to B?
   Show answer

   3. Direct A-B is 4, but A-C-B is 2 + 1 = 3.

3. In the trace graph, what is the shortest distance from A to D?
   Show answer

   8. A-C-B-D = 2 + 1 + 5 = 8 (A-C-D is also 2 + 8 = 10).

4. In what order are the vertices visited (made permanent) when Dijkstra's algorithm runs from A on the trace graph?
   Show answer

   A, C, B, D, E, F. Smallest distance first each time: A, C, B, D, E, F.

5. In the trace graph, edge D-E is removed. What is the new shortest distance from A to E?
   Show answer

   12. Without D-E: A-C-E = 12 or A-C-B-D-F-E = 2 + 1 + 5 + 6 + 3 = 17: so 12.

6. Why is Dijkstra's algorithm described as greedy?
   • It tries every possible path
   • It uses a heuristic estimate of distance to the target
   • At each step it permanently settles the unvisited vertex with the smallest current distance
   • It always takes the edge with the largest weight
   Show answer

   At each step it permanently settles the unvisited vertex with the smallest current distance. It makes the locally best choice each time, which works because weights are not negative.

7. Why must Dijkstra's algorithm not be used with negative edge weights?
   • A settled vertex's distance could later be reduced by a negative edge, so 'final' distances might be wrong
   • Negative numbers cannot be stored
   • The graph would have no edges
   • It would always loop forever
   Show answer

   A settled vertex's distance could later be reduced by a negative edge, so 'final' distances might be wrong. The greedy choice relies on distances never decreasing.

8. What is the 'previous vertex' record used for?
   • Counting the number of edges
   • Tracing the shortest path back from the target to the start
   • Storing the heuristic
   • Choosing the start vertex
   Show answer

   Tracing the shortest path back from the target to the start. Follow previous links back from the target.

Practise with instant feedback Print this lesson

Sources

• Pearson Edexcel International Advanced Subsidiary and Advanced Level in Computer Science specification (2026), Issue 1
• Pearson Edexcel IAL Computer Science sample assessment materials (Unit 3 paper, resource booklet and mark scheme)

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