Shortest Path: Single Source
Dijkstra's algorithm — closest first, then relaxWhat is the quickest way from one place to all the others? Dijkstra's algorithm keeps a distance for every vertex (∞ at first). It repeatedly takes the closest vertex that is not final yet — nothing can reach it more cheaply any more — and relaxes its neighbours: is the route through this vertex shorter than what they have? The priority queue always holds the next vertex to finalise.
- Single sourcedistances from ONE start vertex
- Finalisethe closest unfinished vertex is final
- Relaxis going through it shorter?
- Positive weightsno negative edges
- Current
- Looking at
- Done
- On the shortest path
Ready
Edges are written A-B:4 (letters A–H, weights 1–99, up to 14 edges) · Keyboard: ← → step · Space play / pause · R reset
Every operation, in plain steps
These are exactly the steps the visualizer animates.
Closest first, then relax
Dijkstra finds the shortest distance from ONE source vertex to every other vertex in a graph with positive weights. dist[v] is the best distance found so far (∞ at the start, 0 for the source). The algorithm repeatedly FINALISES the unfinished vertex with the smallest distance — nothing can reach it more cheaply any more — and then RELAXES its neighbours: is going through this vertex shorter than what they have? parent[v] remembers the way, so the path can be read backwards.
int dist[V]; // best distance found so far (INF at the start)
int parent[V]; // the vertex before v on that route
int done[V]; // 1 once dist[v] is final
dist[src] = 0;
for (count = 0; count < V; count++) {
int u = vertex with the smallest dist that is not done yet;
done[u] = 1; // final!
for (each edge u -> v with weight w)
if (!done[v] && dist[u] + w < dist[v]) { // relax
dist[v] = dist[u] + w;
parent[v] = u;
}
}
The algorithm
- dist[source] = 0, every other vertex ∞.
- Pick the unfinished vertex u with the smallest dist: it is FINAL.
- Relax every edge u → v: if dist[u] + w < dist[v], update dist[v] and parent[v].
- Repeat until every reachable vertex is final.
Why is "closest first" safe?
- Any other route to u would first pass through an unfinished vertex.
- That vertex is at least as far as u (we picked the smallest).
- Weights are positive, so going further only adds distance.
- So no route can beat dist[u]: it is final.
Relaxing an edge
- Edge u → v with weight w, u final.
- Candidate = dist[u] + w.
- Candidate < dist[v]: better route found, update dist and parent.
- Otherwise keep the old route.
Reading the path
- Start at the target t.
- Follow parent[t], parent[parent[t]], … back to the source.
- Reverse the list: that is the route.
- dist[t] = ∞ means t cannot be reached.
Not for negative weights
- A negative edge could make a final vertex cheaper later.
- That breaks the "closest first is final" argument.
- For negative weights use Bellman–Ford instead.
- The weights in this lab are 1 to 99.
Dijkstra vs BFS
- BFS: every edge counts as 1, a queue gives the shortest path.
- Dijkstra: edges have weights, a PRIORITY queue gives the shortest path.
- With all weights equal, Dijkstra behaves like BFS.
- Both reach each vertex through the best route known so far.
Pseudocode
Language-independent steps. The visualizer shows the same logic in C, Python and Java.
How fast is each operation?
V = vertices, E = edges. With a simple array the "smallest dist" search costs O(V) each time, so O(V²) overall. With a binary heap every update costs O(log V): O((V + E) log V).
| Operation | Best | Average | Worst | Speed |
|---|---|---|---|---|
| Dijkstra (array) | O(V²) |
O(V²) |
O(V²) |
Grows with n |
| Dijkstra (binary heap) | O((V + E) log V) |
O((V + E) log V) |
O((V + E) log V) |
Grows with n |
| Read a path (parent[ ]) | O(1) |
O(V) |
O(V) |
Grows with n |
Shortest-path algorithms
| BFS | Dijkstra | Bellman–Ford | Floyd–Warshall | |
|---|---|---|---|---|
| Answers | One source (unweighted) | One source (weighted) | One source (weighted) | All pairs |
| Weights | None (every edge = 1) | Positive only | Negative allowed | Negative allowed (no negative cycle) |
| Helper | Queue | Priority queue | None (V − 1 rounds) | Distance table |
| Time | O(V + E) | O(V²) / O((V + E) log V) | O(V × E) | O(V³) |
Dijkstra: what the table holds
| Column | Meaning |
|---|---|
| dist | The best distance found so far from the source (∞ = not reached yet) |
| parent | The vertex just before it on that route |
| done | The distance is final — it never changes again |
Check your understanding
Answer each question — you will see the explanation straight away.
At each step, which vertex does Dijkstra finalise?
The unfinished vertex with the smallest dist cannot be reached more cheaply any more, so its distance is final.
What does "relaxing" an edge u → v mean?
If dist[u] + w < dist[v], the new route is better: dist[v] and parent[v] are updated.
Why does Dijkstra's algorithm not work with negative edge weights?
The argument "nothing can reach a finalised vertex more cheaply" needs positive weights. A negative edge breaks it.
Dijkstra ends with dist[F] = ∞. What does that tell you?
∞ is only lowered by a real route. If it is still ∞ at the end, there is no route from the source to F.
How do you get the shortest PATH (not just its length) from Dijkstra's result?
parent[v] is the vertex just before v on its best route. Following it backwards from the target gives the whole path (in reverse).
What is the time complexity of Dijkstra with a simple array (no heap)?
Finding the smallest dist among the unfinished vertices costs O(V), and it is done V times.
If all edge weights are 1, Dijkstra behaves like…
With equal weights, the closest vertex is always the one discovered earliest — exactly the order of a BFS queue.
The shortest route from A to D goes A → C → B → D. What is parent[D] when Dijkstra has finished?
parent[v] is the vertex just before v on the best route: the vertex before D is B.
Graphs quiz
Test yourself: 5 questions, 70% to pass. Create a free account to take the quiz, save your progress and work towards the certificate.