Dijkstra's Shortest Path Algorithm
debt(d7/e3/b3/t7)
Closest to 'only careful code review or runtime testing' (d7). The detection_hints list blackfire and xdebug as tools, but these are profilers that only reveal the O(V²) performance issue under load — they won't catch the negative-weight correctness bug at all. There's no static analyzer that detects 'you used Dijkstra on a graph with negative edges.' The algorithm silently produces wrong answers unless you manually test edge cases or review the code knowing what to look for.
Closest to 'simple parameterised fix' (e3). The quick_fix says 'Replace linear-scan minimum with SplMinHeap' which is a localized refactor within one component. Adding a negative-weight check is also a small addition. Neither requires touching multiple files or architectural changes, but it's more than a one-line swap since you're restructuring the loop logic.
Closest to 'localised tax' (b3). Dijkstra is typically implemented once in a utility/service class and called from elsewhere. The choice doesn't spread load-bearing dependencies across the codebase — it's contained to the pathfinding component. Wrong implementation slows that feature down, but other maintainers don't need to understand graph algorithms to work on unrelated parts of the system.
Closest to 'serious trap' (t7). The misconception field explicitly states developers believe Dijkstra works with negative edge weights when it does not. This contradicts intuition from BFS (which handles all unweighted graphs uniformly) and the general expectation that 'shortest path algorithm' means 'finds shortest path.' A competent developer unfamiliar with the constraint will confidently apply it to negative-weight graphs and get silent wrong answers.
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;
}