🛤️ Dijkstra's Shortest Path

<?php
function dijkstra(array $graph, int $source): array {
    $n = count($graph);
    $dist = array_fill(0, $n, PHP_INT_MAX);
    $dist[$source] = 0;
    $visited = array_fill(0, $n, false);

    // Min-heap: [node, distance]
    $pq = new SplPriorityQueue();
    $pq->insert([$source, 0], 0); // PHP uses max-heap, negate for min

    while (!$pq->isEmpty()) {
        [$u, $d] = $pq->extract();
        $d = -$d; // Restore positive distance

        if ($visited[$u]) continue;
        $visited[$u] = true;

        foreach ($graph[$u] as [$v, $weight]) {
            if (!$visited[$v] && $dist[$u] + $weight < $dist[$v]) {
                $dist[$v] = $dist[$u] + $weight;
                $pq->insert([$v, -$dist[$v]], -$dist[$v]);
            }
        }
    }
    return $dist;
}

// Graph: node => [ [neighbor, weight], ... ]
$graph = [
    0 => [[1,4], [2,1]],
    1 => [[3,1]],
    2 => [[1,2], [3,5]],
    3 => [],
];

$dists = dijkstra($graph, 0);
print_r($dists); // [0=>0, 1=>3, 2=>1, 3=>4]