Dijkstra – shortest path with weights, SplMinHeap, e-commerce applications

Dijkstra’s algorithm finds the shortest path in a weighted graph – the generalisation of BFS for graphs where edges have costs. It is the foundation of GPS navigation, network routing, and in e-commerce it appears in warehouse routing, delivery zone assignment, and shipping cost calculations. I implement it in PHP with SplMinHeap and show practical applications.

The problem – weighted shortest path

<?php

// Weighted graph as adjacency list with costs
// [node => [neighbour => cost]]
$graph = [
    'A' => ['B' => 4, 'C' => 2],
    'B' => ['A' => 4, 'D' => 3, 'E' => 1],
    'C' => ['A' => 2, 'B' => 1, 'D' => 5],
    'D' => ['B' => 3, 'C' => 5, 'E' => 2],
    'E' => ['B' => 1, 'D' => 2],
];

// Find shortest path from A to D
// Possible paths:
// A -> B -> D: cost 4 + 3 = 7
// A -> C -> B -> D: cost 2 + 1 + 3 = 6
// A -> C -> D: cost 2 + 5 = 7
// A -> B -> E -> D: cost 4 + 1 + 2 = 7
// Shortest: A -> C -> B -> D with cost 6

Dijkstra implementation with SplMinHeap

<?php

declare(strict_types=1);

function dijkstra(array $graph, string $start): array
{
    // distances[node] = shortest known distance from start
    $distances = array_fill_keys(array_keys($graph), PHP_FLOAT_MAX);
    $distances[$start] = 0;

    // previous[node] = the node we came from on the shortest path
    $previous = array_fill_keys(array_keys($graph), null);

    // Priority queue: SplMinHeap pops the smallest element first
    $heap = new class extends \SplMinHeap {
        protected function compare(mixed $a, mixed $b): int
        {
            return $b['cost'] <=> $a['cost']; // min-heap by cost
        }
    };
    $heap->insert(['node' => $start, 'cost' => 0]);

    $visited = [];

    while (!$heap->isEmpty()) {
        ['node' => $current, 'cost' => $currentCost] = $heap->extract();

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

        foreach ($graph[$current] ?? [] as $neighbour => $edgeCost) {
            if (isset($visited[$neighbour])) continue;

            $newCost = $currentCost + $edgeCost;

            if ($newCost < $distances[$neighbour]) {
                $distances[$neighbour] = $newCost;
                $previous[$neighbour]  = $current;
                $heap->insert(['node' => $neighbour, 'cost' => $newCost]);
            }
        }
    }

    return ['distances' => $distances, 'previous' => $previous];
}

// Reconstruct the actual path from start to end
function getPath(array $previous, string $start, string $end): array
{
    $path    = [];
    $current = $end;

    while ($current !== null) {
        array_unshift($path, $current);
        $current = $previous[$current];
    }

    return $path[0] === $start ? $path : []; // return empty if no path
}

// Find shortest path from A to D
$result = dijkstra($graph, 'A');
$path   = getPath($result['previous'], 'A', 'D');
$cost   = $result['distances']['D'];

echo "Shortest path: " . implode(' -> ', $path) . "\n"; // A -> C -> B -> D
echo "Total cost: {$cost}\n";                            // 6

Practical application: nearest warehouse

<?php

declare(strict_types=1);

// Model cities and distances as a graph
// Find which warehouse can fulfil the order with the lowest shipping cost

class ShippingRouteOptimiser
{
    public function __construct(
        private array $distanceMatrix // [city => [city => distance_km]]
    ) {}

    public function findCheapestWarehouse(
        string $customerCity,
        array $warehouseLocations,
        float $costPerKm = 0.50
    ): array {
        $result = dijkstra($this->distanceMatrix, $customerCity);

        $options = [];
        foreach ($warehouseLocations as $warehouseCity) {
            $distance = $result['distances'][$warehouseCity] ?? PHP_FLOAT_MAX;
            $route    = getPath($result['previous'], $customerCity, $warehouseCity);

            $options[] = [
                'warehouse' => $warehouseCity,
                'distance'  => $distance,
                'cost'      => round($distance * $costPerKm, 2),
                'route'     => $route,
            ];
        }

        // Sort by cost
        usort($options, fn($a, $b) => $a['cost'] <=> $b['cost']);
        return $options;
    }
}

$distanceMatrix = [
    'Krakow'   => ['Warsaw' => 295, 'Wroclaw' => 270, 'Katowice' => 75],
    'Warsaw'   => ['Krakow' => 295, 'Gdansk' => 340, 'Wroclaw' => 345],
    'Wroclaw'  => ['Krakow' => 270, 'Warsaw' => 345, 'Poznan' => 175],
    'Katowice' => ['Krakow' => 75,  'Wroclaw' => 200, 'Warsaw' => 310],
    'Gdansk'   => ['Warsaw' => 340, 'Poznan' => 320],
    'Poznan'   => ['Wroclaw' => 175, 'Gdansk' => 320, 'Warsaw' => 310],
];

$optimiser = new ShippingRouteOptimiser($distanceMatrix);
$options   = $optimiser->findCheapestWarehouse(
    'Krakow',
    ['Wroclaw', 'Warsaw', 'Katowice']
);

foreach ($options as $option) {
    echo sprintf(
        "%s: %d km, %.2f PLN (route: %s)\n",
        $option['warehouse'],
        $option['distance'],
        $option['cost'],
        implode(' -> ', $option['route'])
    );
}
// Katowice: 75 km, 37.50 PLN (route: Krakow -> Katowice)
// Wroclaw: 270 km, 135.00 PLN (route: Krakow -> Wroclaw)
// Warsaw: 295 km, 147.50 PLN (route: Krakow -> Warsaw)

Time complexity

Summary

Dijkstra with SplMinHeap is the practical choice for graphs up to thousands of nodes – the complexity is excellent and the implementation is clean. The warehouse routing example shows a direct e-commerce application: given a customer location and multiple warehouse locations, find the cheapest fulfilment source by shipping distance. The same approach works for delivery zone assignment, multi-carrier routing optimisation, and any problem that reduces to “shortest path in a weighted graph”.