Dijkstra’s algorithm – shortest path in a graph, PHP implementation

Dijkstra’s algorithm is a classic shortest path algorithm for weighted graphs with non-negative weights. It runs in O((V + E) log V) with a priority queue, where V is the number of vertices and E the number of edges. Practical applications include routing, GPS navigation, recommendation systems and network optimisation. I show a PHP implementation with a priority queue and two real usage examples.

Algorithm idea

Dijkstra starts from the source node with distance 0. All other nodes have distance infinity. Each iteration picks the unvisited node with the smallest known distance and updates its neighbours’ distances. Key property: once a node is visited its distance is already optimal.

Graph:
A --(4)--> B
A --(2)--> C
C --(1)--> B
B --(3)--> D
C --(5)--> D

Shortest path A to D:
A(0) -> C(2) -> B(3) -> D(6)  -- cost 6
A(0) -> B(4) -> D(7)          -- cost 7
A(0) -> C(2) -> D(7)          -- cost 7

Result: A -> C -> B -> D, cost = 6

PHP implementation

<?php

declare(strict_types=1);

class Graph
{
    /** @var array<string, array<string, float>> */
    private array $edges = [];

    public function addEdge(string $from, string $to, float $weight, bool $bidirectional = false): void
    {
        $this->edges[$from][$to] = $weight;
        if ($bidirectional) {
            $this->edges[$to][$from] = $weight;
        }
    }

    public function getNeighbours(string $node): array { return $this->edges[$node] ?? []; }
    public function getNodes(): array                  { return array_keys($this->edges); }
}

class DijkstraResult
{
    public function __construct(
        public readonly array $distances,
        public readonly array $previous,
    ) {}

    public function getPath(string $target): array
    {
        $path = [];
        $node = $target;

        while ($node !== null) {
            array_unshift($path, $node);
            $node = $this->previous[$node] ?? null;
        }

        return $path;
    }

    public function getDistance(string $target): float
    {
        return $this->distances[$target] ?? INF;
    }
}

class Dijkstra
{
    public function shortestPath(Graph $graph, string $source): DijkstraResult
    {
        $distances = [];
        $previous  = [];
        $visited   = [];

        foreach ($graph->getNodes() as $node) {
            $distances[$node] = INF;
            $previous[$node]  = null;
        }
        $distances[$source] = 0.0;

        $pq = new \SplMinHeap();
        $pq->insert([0.0, $source]);

        while (!$pq->isEmpty()) {
            [$cost, $node] = $pq->extract();

            if (isset($visited[$node])) continue;
            $visited[$node] = true;

            foreach ($graph->getNeighbours($node) as $neighbour => $weight) {
                if (isset($visited[$neighbour])) continue;

                $newDist = $distances[$node] + $weight;

                if ($newDist < $distances[$neighbour]) {
                    $distances[$neighbour] = $newDist;
                    $previous[$neighbour]  = $node;
                    $pq->insert([$newDist, $neighbour]);
                }
            }
        }

        return new DijkstraResult($distances, $previous);
    }
}

// Usage
$graph = new Graph();
$graph->addEdge('Warsaw',  'Lodz',    130, bidirectional: true);
$graph->addEdge('Warsaw',  'Lublin',  170, bidirectional: true);
$graph->addEdge('Lodz',    'Wroclaw', 210, bidirectional: true);
$graph->addEdge('Lodz',    'Poznan',  210, bidirectional: true);
$graph->addEdge('Lublin',  'Krakow',  290, bidirectional: true);
$graph->addEdge('Wroclaw', 'Krakow',  270, bidirectional: true);
$graph->addEdge('Poznan',  'Wroclaw', 180, bidirectional: true);
$graph->addEdge('Krakow',  'Katowice', 80, bidirectional: true);

$dijkstra = new Dijkstra();
$result   = $dijkstra->shortestPath($graph, 'Warsaw');

$path = $result->getPath('Krakow');
echo "Shortest route Warsaw -> Krakow:\n";
echo implode(' -> ', $path) . "\n";
echo "Distance: " . $result->getDistance('Krakow') . " km\n";
// Warsaw -> Lodz -> Wroclaw -> Krakow: 610 km

Application – warehouse network routing

<?php

declare(strict_types=1);

class ShippingRouter
{
    private Graph $graph;
    private Dijkstra $dijkstra;

    public function __construct()
    {
        $this->graph    = new Graph();
        $this->dijkstra = new Dijkstra();
        $this->buildNetwork();
    }

    private function buildNetwork(): void
    {
        $routes = [
            ['WH_Warsaw',   'HUB_Central', 15.0],
            ['WH_Krakow',   'HUB_Central', 18.0],
            ['WH_Gdansk',   'HUB_North',   12.0],
            ['WH_Wroclaw',  'HUB_Central', 14.0],
            ['HUB_Central', 'HUB_North',   8.0],
            ['HUB_Central', 'HUB_South',   10.0],
            ['HUB_North',   'DEL_Poznan',  6.0],
            ['HUB_Central', 'DEL_Lodz',    5.0],
            ['HUB_South',   'DEL_Katowice', 7.0],
        ];

        foreach ($routes as [$from, $to, $cost]) {
            $this->graph->addEdge($from, $to, $cost, bidirectional: true);
        }
    }

    public function findCheapestRoute(string $source, string $destination): array
    {
        $result = $this->dijkstra->shortestPath($this->graph, $source);

        return [
            'path'     => $result->getPath($destination),
            'cost'     => $result->getDistance($destination),
            'possible' => $result->getDistance($destination) !== INF,
        ];
    }
}

$router = new ShippingRouter();
$route  = $router->findCheapestRoute('WH_Warsaw', 'DEL_Katowice');

if ($route['possible']) {
    echo "Route: " . implode(' -> ', $route['path']) . "\n";
    echo "Cost: "  . $route['cost'] . " PLN\n";
}

Complexity and variants

Dijkstra does not work with negative weights – Bellman-Ford handles that. For undirected graphs with equal weights, BFS (O(V+E)) is sufficient.

Summary

Dijkstra is the foundation of most routing systems. The SplMinHeap implementation runs in O((V+E) log V) and is sufficient for graphs up to a few thousand nodes. In PHP note that SplMinHeap compares elements using the comparison operator – arrays are compared lexicographically, so the [cost, node] pair works correctly. For very large graphs (millions of nodes) use specialised libraries or external routing services.