Graph

Dijkstra’s Algorithm

Find the shortest path distances from a start node by repeatedly choosing the node with the smallest tentative distance and relaxing its edges.

Dijkstra’s Algorithm becomes difficult when learners try to track tentative distances, visited states, and parent updates all at once. This page separates those ideas into a clear step-by-step flow.

The key teaching flow is: initialize distances → pick the smallest tentative node → relax outgoing edges → record parents → build the shortest-path tree.

Watch Visualization View Pseudocode

Quick Facts

Main Idea

Always expand the unvisited node with the smallest tentative distance from the source.

Core Operation

Relaxation checks whether going through the current node improves a neighbor’s tentative distance.

Parent Pointers

Every successful improvement records where that better path came from.

Important Condition

Dijkstra’s Algorithm assumes edge weights are nonnegative.

Key Idea

Dijkstra’s Algorithm is not just “walking through the graph.” It is a disciplined process for improving distance estimates until the best known value becomes final.

The most important mental model is: tentative distances compete, and the smallest confirmed one is finalized next.

Visualization

This visualization begins at A, shows tentative values on the graph, highlights each selected node, and makes every successful relaxation visible. It then extracts the final shortest-path tree from the recorded parent pointers.

Watch actively: pause before each step and predict which node will be selected next and which neighbor values will change.

How It Works

Initialize

Set the source node to distance 0 and all other nodes to ∞.

Choose the Smallest Tentative Node

Among all unvisited nodes, pick the one with the smallest tentative distance.

Relax Outgoing Edges

Test whether going through the current node gives any neighbor a shorter path.

Record Parents

When a distance improves, update the parent pointer so the final shortest-path tree can be built later.

What Relaxation Means

Old Value vs New Candidate

Relaxation compares the current tentative distance of a neighbor with a new candidate path through the active node.

Improve Only When Better

A value changes only if the new path is shorter than the old tentative value.

Parent Changes with Improvement

When a shorter path is found, the parent pointer is updated to match that better route.

Finalized Means Finished

Once a node is selected as the smallest tentative unvisited node, its shortest-path distance is finalized.

In your current lesson flow, this is the most important reasoning step: understanding why a tentative value stays the same or improves. :contentReference[oaicite:1]{index=1}

Example Reasoning from the Lesson

The lesson uses nodes A, B, C, D, E, Z and emphasizes how values improve over time. Two especially useful examples are:

C improves from 6 to 5 through B
Z improves from 16 to 13 through D

These examples help learners see that Dijkstra’s Algorithm is not about one fixed guess at the start. Distances can improve as better paths are discovered.

From Distances to the Shortest-Path Tree

The final shortest-path tree is not built separately from scratch. It emerges from the history of successful parent updates.

Once all reachable nodes are finalized, the tree is formed by taking the parent edge of each node and connecting those edges back to the source.

Why It Matters

Shortest-Path Reasoning

Dijkstra’s Algorithm is a foundational method for understanding weighted graph search.

Algorithmic State Tracking

It teaches how an algorithm maintains and updates internal state over time.

Graph Decision-Making

Learners practice choosing the next node based on evidence, not guesswork.

Tree Interpretation

It helps students distinguish between the algorithmic process and the final structure that process produces.

Shortest-Path Tree vs Minimum Spanning Tree

Shortest-Path Tree

Optimizes the distance from one source node to every reachable node.

Minimum Spanning Tree

Minimizes the total edge weight of the tree across the whole graph, without being tied to one source.

This is one of the most common misconceptions in the topic, so it is worth making explicit. :contentReference[oaicite:2]{index=2}

Pseudocode

This pseudocode shows the core shortest-path process:

DIJKSTRA(G, source):
    for each vertex v in G:
        dist[v] = ∞
        parent[v] = null
        visited[v] = false

    dist[source] = 0

    while there exists an unvisited vertex:
        u = unvisited vertex with smallest dist[u]
        visited[u] = true

        for each neighbor v of u:
            if visited[v] == false:
                newDist = dist[u] + weight(u, v)

                if newDist < dist[v]:
                    dist[v] = newDist
                    parent[v] = u

The important detail is that parent pointers are updated at the same time as improved distances. That is what makes the final shortest-path tree possible.

Common Confusions

“Visited” means seen once

Not exactly. In Dijkstra’s Algorithm, visited means the node’s shortest distance has been finalized.

Relaxation always changes a value

No. A relaxation changes a neighbor only when the new candidate path is actually shorter.

The shortest-path tree is built separately

No. It comes directly from the final parent pointers recorded during successful relaxations.

Dijkstra works with negative edges

No. Standard Dijkstra’s Algorithm assumes nonnegative edge weights.

Outcome

After this lesson, learners should be able to explain tentative distances, predict which node is selected next, describe what relaxation does, and show how parent pointers form the final shortest-path tree.

Back to Home