Graphs · step 9 of 14

Shortest paths with Dijkstra

Dijkstra computes shortest paths from one source to all vertices in a graph with non-negative weights. It repeatedly finalises the unvisited vertex with the smallest tentative distance and relaxes its outgoing edges. The non-negativity requirement is essential: a negative edge can improve a path after a vertex has been finalised, which breaks the whole argument.

Practise shortest paths with dijkstra free → All Graphs subtopics

✓ Unlimited questions · marked criterion by criterion · no card needed

Method: how to approach it

The order below is what examiners expect to see, and each step carries its own marks.

Initialise the tableSource distance 0, all others ∞, all vertices unvisited. Keep a predecessor column to reconstruct paths.
Pick the smallest unvisited distanceThat vertex is now final — its distance cannot improve, since all remaining routes are already at least as long.
Relax its neighboursFor each neighbour v, if dist(u) + w(u,v) < dist(v), update the distance and set the predecessor to u.
Repeat and reconstructContinue until all vertices are visited, then follow predecessors backwards from the target.

Worked example

Find the shortest path from A to D with edges AB=1, AC=4, BC=2, BD=6, CD=3.

Start: A = 0, others ∞. Visit A; relax to B = 1, C = 4.
Smallest unvisited is B (1). Relax: C via B = 1 + 2 = 3 < 4, so C = 3 (pred B). D via B = 1 + 6 = 7.
Smallest unvisited is C (3). Relax: D via C = 3 + 3 = 6 < 7, so D = 6 (pred C).
Visit D at 6. Reconstruct predecessors: D ← C ← B ← A.

Answer. Shortest distance A to D is 6, along the path A → B → C → D.

Where marks get dropped

These are the specific errors that cost credit on shortest paths with dijkstra questions — QED's rubric penalises each of them separately.

Running Dijkstra with negative edge weights. It can silently return wrong answers — use Bellman–Ford instead.
Finalising a vertex before checking every relaxation from the current one. Always relax all neighbours before moving on.
Forgetting the predecessor column, which makes reconstructing the actual path impossible from distances alone.

Practise this until it is automatic

Unlimited fresh questions

QED generates new shortest paths with dijkstra problems on demand at warm-up, exam and challenge level, so you can drill this one skill until it stops costing you marks.

Marked like an examiner

Every answer is scored against a point-by-point rubric with partial credit, so you see exactly which step of the method broke down — not just a tick or a cross.

Answer in real notation

A one-tap symbol palette, a visual equation editor and a truth-table builder — or photograph your handwritten working and QED converts it to LaTeX.

Saved to your library

Every question you generate is kept and re-takeable as a timed exam, and your Graphs mastery is tracked so you know when this is exam-ready.

Shortest paths with Dijkstra — frequently asked questions

Why must weights be non-negative?

The correctness argument assumes the chosen minimum can never be improved later. A negative edge could reduce a finalised distance, invalidating it.

What is the complexity?

O((V + E) log V) with a binary heap, or O(V²) with a simple array scan — the latter is better for dense graphs.

How does A* differ?

A* adds an admissible heuristic estimate of the remaining distance to the priority, guiding the search towards the target. With a zero heuristic it reduces exactly to Dijkstra.

The rest of Graphs

Terminology, connectivity, trees, paths and cycles. Each subtopic below has its own method, worked example and mark-losing traps.

Ready to make shortest paths with dijkstra exam-proof?

Generate your first questions free — no card, no setup, no personal data stored. Practise until the method is second nature.

Start practising free →