← Iris
Lab / Experiment

Dijkstra’s Algorithm

Build a weighted graph by placing nodes and drawing edges. Pick a start and end node, then watch Dijkstra’s algorithm explore outward — always expanding the closest unvisited node — until it finds the shortest path. The greedy strategy that solves routing, navigation, and network optimization.

Add nodes

Algorithm State

Nodes 0
Edges 0
Visited 0
Path cost —
Steps 0

Node colors

Start node
End node
Shortest path
Visited / settled
In priority queue
Unvisited
Animation speed 5
Add nodes mode: click to place nodes  ·  Add edges mode: click two nodes to connect them (weight = distance)  ·  Set start/end: click a node to mark it  ·  Run: animate the full algorithm  ·  Step: advance one iteration at a time  ·  Right-click a node to delete it

What’s happening

Dijkstra’s algorithm

Edsger Dijkstra published this algorithm in 1959. It finds the shortest path from a source node to all other nodes in a graph with non-negative edge weights. The key insight is greedy: always process the unvisited node with the smallest known distance. Once a node is “settled” (removed from the priority queue), its distance is guaranteed to be optimal.

How it works

Initialize all distances to infinity except the source (distance 0). Place the source in a priority queue. Repeatedly: extract the node with minimum distance, mark it as visited, and for each neighbor, check if going through this node offers a shorter path. If so, update the neighbor’s distance and predecessor. The algorithm terminates when the destination is settled or the queue is empty.

The priority queue

The priority queue (min-heap) is what makes Dijkstra efficient. Without it, you’d scan all nodes to find the minimum — O(V²) total. With a binary heap, each extraction costs O(log V), giving O((V + E) log V) overall. With a Fibonacci heap, it’s theoretically O(V log V + E), though the constant factors often make binary heaps faster in practice.

Why non-negative weights?

Dijkstra’s greedy strategy assumes that adding an edge can never decrease the total path cost. With negative weights, a settled node might later be reached by a shorter path through a negative edge, violating the algorithm’s core invariant. For graphs with negative weights, you need the Bellman-Ford algorithm, which is slower but handles the general case.

Pseudocode

function Dijkstra(graph, source):
    dist[source] ← 0
    for each vertex v ≠ source:
        dist[v] ← ∞
    Q ← priority queue of all vertices

    while Q is not empty:
        u ← Q.extract_min()
        for each neighbor v of u:
            alt ← dist[u] + weight(u, v)
            if alt < dist[v]:
                dist[v] ← alt
                prev[v] ← u
                Q.decrease_key(v, alt)

Dijkstra’s algorithm is the foundation of GPS navigation (finding routes on road networks), network routing protocols (OSPF), and game AI pathfinding. Its descendant A* adds a heuristic to explore more efficiently toward a specific goal.