Algorytm Dijkstry – najkrótsza ścieżka w grafie, implementacja PHP

Algorytm Dijkstry to klasyczny algorytm wyszukiwania najkrótszej ścieżki w grafie ważonym z nieujemnymi wagami. Działa w O((V + E) log V) z kolejką priorytetową, gdzie V to liczba wierzchołków a E krawędzi. Praktyczne zastosowania to routing, nawigacja GPS, systemy rekomendacji i optymalizacja sieci. Pokażę implementację w PHP z kolejką priorytetową i dwa realne przykłady użycia.

Idea algorytmu

Dijkstra startuje z węzła źródłowego z odległością 0. Wszystkie pozostałe węzły mają odległość nieskończoną. W każdej iteracji wybieramy nieodwiedzony węzeł z najmniejszą znana odległością i aktualizujemy odległości jego sąsiadów. Kluczowa właściwość: gdy węzeł zostanie odwiedzony jego odległość jest już optymalna.

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

Najkrótsza ścieżka A do D:
A(0) -> C(2) -> B(3) -> D(6)  -- koszt 6
A(0) -> B(4) -> D(7)          -- koszt 7
A(0) -> C(2) -> D(7)          -- koszt 7

Wynik: A -> C -> B -> D, koszt = 6

Implementacja w PHP

<?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;
        }
    }

    /** @return array<string, float> */
    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,  // node => distance from source
        public readonly array $previous,   // node => previous node on shortest path
    ) {}

    // Odtwórz ścieżkę od source do target
    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   = [];

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

        // Kolejka priorytetowa: [koszt, węzeł]
        // PHP nie ma wbudowanej min-heap - symulujemy przez SplMinHeap
        $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);
    }
}

// Użycie - przykład z trasy między miastami
$graph = new Graph();
$graph->addEdge('Warszawa', 'Lodz',    130, bidirectional: true);
$graph->addEdge('Warszawa', '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, 'Warszawa');

$path = $result->getPath('Krakow');
echo "Najkrótsza trasa Warszawa -> Kraków:\n";
echo implode(' -> ', $path) . "\n";
echo "Dystans: " . $result->getDistance('Krakow') . " km\n";
// Warszawa -> Lodz -> Wroclaw -> Krakow: 610 km

Zastosowanie – routing w sieci magazynów

<?php

declare(strict_types=1);

// Znajdź najtańszą trasę wysyłki między magazynami
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
    {
        // Węzły: magazyny i huby logistyczne
        // Wagi: koszt transportu w PLN/paczka
        $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 "Trasa: " . implode(' -> ', $route['path']) . "\n";
    echo "Koszt: " . $route['cost'] . " PLN\n";
}

Złożoność i warianty

Dijkstra nie działa z ujemnymi wagami – do tego służy algorytm Bellmana-Forda. Dla grafów nieskierowanych i jednakowych wag wystarczy BFS (O(V+E)).

Podsumowanie

Dijkstra to fundament większości systemów routingu. Implementacja z SplMinHeap działa w O((V+E) log V) i jest wystarczająca dla grafów do kilku tysięcy węzłów. W PHP warto pamiętać że SplMinHeap porównuje elementy przez operator porównania – tablice porównywane są leksykograficznie, więc para [koszt, węzeł] działa poprawnie. Dla bardzo dużych grafów (miliony węzłów) lepiej użyć specjalizowanych bibliotek lub zewnętrznych serwisów routingu.