Dijkstra's Shortest Path Algorithm

Also Known As

TL;DR

Explanation

Dijkstra's algorithm maintains a set of unvisited nodes and a distance table initialised to infinity for all nodes except the source (distance 0). At each step it picks the unvisited node with the smallest known distance, relaxes its neighbours (updates their distance if a shorter path is found via the current node), and marks it visited. With a min-heap (priority queue) the time complexity is O((V + E) log V) where V is vertices and E is edges. It cannot handle negative edge weights — use Bellman-Ford for those. Common applications: GPS navigation, network routing (OSPF), game pathfinding, and dependency resolution. In PHP it appears in graph-based recommendation engines, delivery route optimisation, and network topology tools.

Diagram

flowchart LR
    subgraph Graph
        A((A<br/>0)) -->|4| B((B<br/>4))
        A -->|2| C((C<br/>2))
        C -->|1| B
        B -->|3| D((D<br/>7))
        C -->|5| D
    end
    subgraph Processing Order
        S1[Visit A dist=0] --> S2[Visit C dist=2]
        S2 --> S3[Visit B dist=3<br/>via A-C-B]
        S3 --> S4[Visit D dist=6<br/>via A-C-B-D]
    end
style A fill:#238636,color:#fff
style S4 fill:#1f6feb,color:#fff

Common Misconception

Why It Matters

Common Mistakes

• Using an array scan to find the minimum distance node instead of a min-heap — O(V²) instead of O((V+E) log V), catastrophic on large graphs.
• Not checking for negative weights before applying Dijkstra — silent wrong answers are worse than an exception.
• Revisiting already-settled nodes — always check if a node has been visited before processing it from the queue.
• Confusing Dijkstra with BFS — BFS finds shortest paths only in unweighted graphs; Dijkstra handles weighted edges.

Code Examples

// O(V²) — linear scan for minimum, no heap:
function dijkstraSlow(array $graph, int $src): array {
    $dist = array_fill(0, count($graph), PHP_INT_MAX);
    $dist[$src] = 0;
    $visited = [];
    while (count($visited) < count($graph)) {
        // Slow: scan all nodes to find min
        $u = -1;
        foreach ($dist as $v => $d) {
            if (!isset($visited[$v]) && ($u === -1 || $d < $dist[$u])) $u = $v;
        }
        $visited[$u] = true;
        foreach ($graph[$u] as [$v, $w]) {
            if ($dist[$u] + $w < $dist[$v]) $dist[$v] = $dist[$u] + $w;
        }
    }
    return $dist;
}

// O((V+E) log V) — min-heap via SplMinHeap:
function dijkstra(array $graph, int $src): array {
    $dist = array_fill(0, count($graph), PHP_INT_MAX);
    $dist[$src] = 0;
    $heap = new SplMinHeap();
    $heap->insert([0, $src]); // [distance, node]

    while (!$heap->isEmpty()) {
        [$d, $u] = $heap->extract();
        if ($d > $dist[$u]) continue; // stale entry
        foreach ($graph[$u] as [$v, $weight]) {
            $newDist = $dist[$u] + $weight;
            if ($newDist < $dist[$v]) {
                $dist[$v] = $newDist;
                $heap->insert([$newDist, $v]);
            }
        }
    }
    return $dist;
}

References

• ↗ https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Tags

Related Terms