Algorytm Dijkstry pomaga w znalezieniu najkrótszej ścieżki w grafie. Mówiąc po ludzku, można go zastosować np. do znalezienia najkrótszej drogi od miejscowości A do miejscowości E. Żeby to działało należy przyjąć, że wierzchołki(V) to skrzyżowania, a wagi krawędzi to odległości pomiędzy miastami.

Algorytm Dijkstry jest wykorzystywany w informatyce na przykład do trasowania pakietów w protokole OSPF(Open Shortest Path First).

Pseudokod algorytmu, źródło wikipedia:

Dijkstra(G,w,s):
   dla każdego wierzchołka v w V[G] wykonaj
      d[v] := nieskończoność
      poprzednik[v] := niezdefiniowane
   d[s] := 0
   Q := V
   dopóki Q niepuste wykonaj
      u := Zdejmij_Min(Q)
      dla każdego wierzchołka v – sąsiada u wykonaj
         jeżeli d[v] > d[u] + w(u, v) to
            d[v] := d[u] + w(u, v)
            poprzednik[v] := u
            Dodaj(Q, v)

   cout <<"Droga wynosi: "<<d[v];

Postanowiłem napisać klasę w PHP, która będzie realizowana algorytm Dijkstry, przy okazji pisania algorytmu skorzystałem z przeładowania metody magicznej __toString() oraz obejścia przeładowania konstruktora.

class Dijkstra
{
    private $graph_array = [];
    private $path = null;

    public function  __construct(Array $graph = null)
    {
        if($graph != null && is_array($graph))
            $this->setGraph($graph);
    }

    public function setGraph(Array $graph)
    {
        $this->graph_array = $graph;
    }

    public function process($source, $target)
    {
        if(count($this->graph_array) < 2)
            return false;

        $vertices = [];
        $neighbours = [];
        foreach ($this->graph_array as $edge)
        {
            array_push($vertices, $edge[0], $edge[1]);
            $neighbours[$edge[0]][] = array("end" => $edge[1], "cost" => $edge[2]);
            $neighbours[$edge[1]][] = array("end" => $edge[0], "cost" => $edge[2]);
        }
        $vertices = array_unique($vertices);

        foreach ($vertices as $vertex)
        {
            $dist[$vertex] = INF;
            $previous[$vertex] = NULL;
        }

        $dist[$source] = 0;
        $Q = $vertices;
        while (count($Q) > 0)
        {
            $min = INF;

            foreach ($Q as $vertex){
                if ($dist[$vertex] < $min) {
                    $min = $dist[$vertex];
                    $u = $vertex;
                }
            }

            $Q = array_diff($Q, array($u));
            if ($dist[$u] == INF || $u == $target)
                break;


            if (isset($neighbours[$u]))
            {
                foreach ($neighbours[$u] as $arr)
                {
                    $alt = $dist[$u] + $arr["cost"];
                    if ($alt < $dist[$arr["end"]])
                    {
                        $dist[$arr["end"]] = $alt;
                        $previous[$arr["end"]] = $u;
                    }
                }
            }
        }
        $path = array();
        $u = $target;
        while (isset($previous[$u]))
        {
            array_unshift($path, $u);
            $u = $previous[$u];
        }
        array_unshift($path, $u);
        $this->path = $path;
    }

    public function returnPath()
    {
        return implode(", ", $this->path);
    }

    public function __toString()
    {
        return $this->returnPath();
    }
}

Klasa realizuje pseudokod i korzystanie z niej sprowadza się do podania w konstruktorze lub w metodzie setGraph(Array) tablicy z odległościami(wagami wierzchołków) pomiędzy określonymi punktami:

$graph_array = array(
    array("a", "b", 6),
    array("a", "c", 5),
    array("a", "f", 18),
    array("b", "c", 7),
    array("b", "d", 3),
    array("c", "d", 14),
    array("c", "f", 1),
    array("d", "e", 10),
    array("e", "f", 6)
);

$alg = new Dijkstra($graph_array);
$alg->process('a','d');
echo $alg.'<br>';
$alg->process('a','e');
echo $alg;

W konstruktorze podaje tablice z odległościami pomiędzy punktami, następnie wywołuje metodę process, która sprawdza najkrótszą ścieżkę pomiędzy punktami a oraz d następnie wypisuje tą ścieżkę(w tym momencie wywołana jest metoda magiczna __toString(). I potem powtarzam to samo dla innej ścieżki.

Rezultatem działania aplikacji będzie wypisanie dwóch ścieżek:

a, b, d
a, c, f, e

W aplikacji korzystam z wielu funkcji operujących na tablicach:

• array_unique($array) zwraca unikalne wartości z tablicy $array
• array_push($array, $e) wstawia element $e na koniec tablicy $array
• array_diff($A, $B) zwraca różnicę(elementy, które występują w zbiorze A i nie występują w zbiorze B)
• array_unshift($array, $e) wstawia element(y) $e na początek tablicy $array

Korzystam również ze stałej matematycznej INF reprezentującej nieskończoność w PHP.