Dijkstra – najkrótsza ścieżka z wagami, SplMinHeap, zastosowania w e-commerce

W maju 2021 pisałem o BFS i DFS dla grafów bez wag. Czas na algorytm Dijkstry – klasyczny algorytm znajdowania najkrótszej ścieżki w grafie z wagami nieujemnymi. Pojawia się wszędzie tam gdzie „najkrótsza” nie oznacza „najmniej kroków”, ale „najmniejszy koszt” – routing, optymalizacja dostaw, recommendation engines.

Kiedy Dijkstra, kiedy BFS?

BFS (z wpisu z 2021) gwarantuje najkrótszą ścieżkę mierzoną liczbą krawędzi – gdy wszystkie krawędzie mają taki sam koszt. Dijkstra działa z wagami – każda krawędź ma przypisany koszt (czas, odległość, cena). Dijkstra nie obsługuje ujemnych wag – do tego służy algorytm Bellmana-Forda.

Implementacja w PHP

<?php

declare(strict_types=1);

class WeightedGraph
{
    private array $edges = [];

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

        if ($bidirectional) {
            $this->edges[$to][$from] = $weight;
        }
    }

    public function getNeighbors(string $vertex): array
    {
        return $this->edges[$vertex] ?? [];
    }

    public function getVertices(): array
    {
        return array_keys($this->edges);
    }
}

function dijkstra(WeightedGraph $graph, string $start): array
{
    $distances = [];
    $previous  = [];
    $visited   = [];

    // Inicjalizacja - wszystkie odległości = nieskończoność
    foreach ($graph->getVertices() as $vertex) {
        $distances[$vertex] = PHP_FLOAT_MAX;
        $previous[$vertex]  = null;
    }

    $distances[$start] = 0;

    // Kolejka priorytetowa - przetwarzaj wierzchołki od najmniejszej odległości
    $queue = new \SplMinHeap();
    $queue->insert([0.0, $start]); // [koszt, wierzchołek]

    while (!$queue->isEmpty()) {
        [$currentDist, $current] = $queue->extract();

        // Pomiń jeśli już odwiedzony lub ta ścieżka jest gorsza
        if (isset($visited[$current]) || $currentDist > $distances[$current]) {
            continue;
        }

        $visited[$current] = true;

        foreach ($graph->getNeighbors($current) as $neighbor => $weight) {
            if (isset($visited[$neighbor])) {
                continue;
            }

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

            if ($newDist < $distances[$neighbor]) {
                $distances[$neighbor] = $newDist;
                $previous[$neighbor]  = $current;
                $queue->insert([$newDist, $neighbor]);
            }
        }
    }

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

// Odtworzenie ścieżki
function reconstructPath(array $previous, string $start, string $end): array
{
    $path = [];
    $node = $end;

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

    // Sprawdź czy ścieżka istnieje
    return $path[0] === $start ? $path : [];
}

Praktyczny przykład – optymalizacja dostaw między miastami

<?php

// Graf miast z czasami przejazdu w minutach
$graph = new WeightedGraph();
$graph->addEdge('Warszawa',  'Łódź',       130);
$graph->addEdge('Warszawa',  'Kraków',      290);
$graph->addEdge('Warszawa',  'Białystok',   185);
$graph->addEdge('Łódź',      'Kraków',      210);
$graph->addEdge('Łódź',      'Wrocław',     190);
$graph->addEdge('Łódź',      'Poznań',      170);
$graph->addEdge('Kraków',    'Katowice',     70);
$graph->addEdge('Kraków',    'Rzeszów',     150);
$graph->addEdge('Wrocław',   'Poznań',      175);
$graph->addEdge('Wrocław',   'Katowice',    180);
$graph->addEdge('Poznań',    'Szczecin',    200);
$graph->addEdge('Katowice',  'Rzeszów',     165);

$result = dijkstra($graph, 'Warszawa');

// Najkrótsza ścieżka do każdego miasta
foreach ($result['distances'] as $city => $distance) {
    if ($distance < PHP_FLOAT_MAX) {
        $path = reconstructPath($result['previous'], 'Warszawa', $city);
        echo sprintf(
            "%-12s: %4d min | Trasa: %s\n",
            $city,
            (int) $distance,
            implode(' -> ', $path)
        );
    }
}

// Warszawa:      0 min | Trasa: Warszawa
// Łódź:        130 min | Trasa: Warszawa -> Łódź
// Białystok:   185 min | Trasa: Warszawa -> Białystok
// Wrocław:     320 min | Trasa: Warszawa -> Łódź -> Wrocław
// Poznań:      300 min | Trasa: Warszawa -> Łódź -> Poznań
// Kraków:      290 min | Trasa: Warszawa -> Kraków
// Katowice:    360 min | Trasa: Warszawa -> Kraków -> Katowice
// Rzeszów:     440 min | Trasa: Warszawa -> Kraków -> Rzeszów
// Szczecin:    500 min | Trasa: Warszawa -> Łódź -> Poznań -> Szczecin

Dijkstra z SplPriorityQueue – czytelniejsza wersja

<?php

declare(strict_types=1);

// Wersja używająca SplPriorityQueue PHP
// Uwaga: SplPriorityQueue sortuje malejąco - negujemy wartości
function dijkstraWithSpl(WeightedGraph $graph, string $start, string $end): array
{
    $distances = [];
    $previous  = [];

    foreach ($graph->getVertices() as $vertex) {
        $distances[$vertex] = PHP_FLOAT_MAX;
    }

    $distances[$start] = 0;

    $pq = new \SplPriorityQueue();
    $pq->setExtractFlags(\SplPriorityQueue::EXTR_BOTH);
    $pq->insert($start, 0); // priorytet = negacja kosztu (większy = wyższy priorytet)

    while (!$pq->isEmpty()) {
        $extracted = $pq->extract();
        $current   = $extracted['data'];
        $cost      = -$extracted['priority']; // odwróć negację

        if ($cost > $distances[$current]) {
            continue; // starsza wersja ścieżki
        }

        if ($current === $end) {
            break; // znaleźliśmy cel
        }

        foreach ($graph->getNeighbors($current) as $neighbor => $weight) {
            $newDist = $distances[$current] + $weight;

            if ($newDist < $distances[$neighbor]) {
                $distances[$neighbor] = $newDist;
                $previous[$neighbor]  = $current;
                $pq->insert($neighbor, -$newDist); // negacja dla min-heap
            }
        }
    }

    return [
        'distance' => $distances[$end] < PHP_FLOAT_MAX ? $distances[$end] : null,
        'path'     => reconstructPath($previous, $start, $end),
    ];
}

$result = dijkstraWithSpl($graph, 'Warszawa', 'Rzeszów');
echo "Najkrótsza droga: {$result['distance']} min\n";
echo "Trasa: " . implode(' -> ', $result['path']) . "\n";
// Najkrótsza droga: 440 min
// Trasa: Warszawa -> Kraków -> Rzeszów

Złożoność i ograniczenia

Gdzie V = liczba wierzchołków, E = liczba krawędzi. Dla rzadkich grafów (mało krawędzi) wersja z SplMinHeap jest optymalna w PHP.

Zastosowania w praktyce PHP/Magento

Dijkstra pojawia się w e-commerce częściej niż myślisz:

• Optymalizacja realizacji zamówień MSI – wybór Source który minimalizuje łączny koszt wysyłki, uwzględniając wagi (koszt wysyłki) zamiast tylko odległości
• Rekomendacje produktów – graf relacji między produktami („kupujący A i B kupili też C”) z wagami opartymi na częstości współwystępowania
• Routing w aplikacjach logistycznych – optymalizacja trasy dla kuriera z wieloma przystankami
• Cache dependency graph – ustalanie kolejności inwalidacji zależnych kluczy cache przy zmianie danych

Podsumowanie

Dijkstra to algorytm który warto mieć pod ręką gdy pojawia się problem „znajdź najtańszą drogę”. Implementacja w PHP z SplMinHeap jest czytelna i wydajna dla grafów typowej wielkości w e-commerce. Kluczowe ograniczenie to ujemne wagi krawędzi – Dijkstra ich nie obsługuje. Przy logistyce z rabatami lub ujemnymi kosztami (np. cashback) trzeba sięgnąć po Bellmana-Forda lub zmodyfikować model danych eliminując ujemne wagi.