Dijkstra

Geschrieben von Joël Mathys.

Problem des kürzesten Weges

Ich habe das erste Mal vom Dijkstra Algorithmus am SOI Tag beim Finale der Kreativaufgabe 2014 gehört. Bei der Kreativaufgabe Cops & Robbers (dem Brettspiel Scottland Yard nachempfunden) ging es darum, entweder den Polizisten zu helfen den Räuber möglichst schnell festzunehmen oder dem Räuber zu helfen möglichst lange vor der Polizei zu fliehen. Die beiden Finalisten nutzten beide den Dijkstra Algorithmus um die kürzesten Wege vom Räuber zu den Polizisten zu finden und je nach Rolle diesen Wegen auszuweichen oder sie zu bentzen um den Räuber zu stellen. Eine Visualisierung der Krativaufgabe ist auf Youtube Watch them fight! [00:25 - 01:27] als Video verfügbar.

Der Dijkstra Algorithmus kommt aber nicht nur in Spielen zum Einsatz, sondern ist auch sonst im Alltag präsent. So brauchen Firmen wie die SBB oder Google den Algorithmus um die kürzesten, schnellsten oder billigsten Wege von A nach B zu finden.

Lösungsansatz

Mithilfe von BFS können wir die kürzesten Wege in ungewichteten Graphen finden. Eine mögliche Lösung wäre es alle gewichteten Kanten durch ungewichtete Kanten zu ersetzten. Dies führt allerdings zu sehr grossen Graphen und ist abhängig vom grössten Kantengewicht.

Gewichtete Graphen (links), können wir auch in ungewichtete Graphen (rechts) verwandeln. Allerdings fügen wir unter Umständen sehr viele Knoten ein, ungefähr so viele wie die Summe aller Kantengewichte. Da diese bei SOI Aufgaben meist bis zu :math:`10^9` gross werden, ist dieser Ansatz nicht effizient.

Mit dem Algorithmus von Edsger W. Dijkstra können wir das Problem in allen Graphen unabhängig von der Grösse der Kantengewichte lösen, solange diese nicht negativ sein können.

Grundidee

Unsere Suche läuft ähnlich ab, als ob wir Wasser in unserem Startknoten \(S\) pumpen würden. Der Algorithmus simuliert nun den Lauf des Wassers. Sobald das Wasser einen Knoten erreicht, wissen wir den kürzesten Weg von \(S\) zum erreichten Knoten. Gäbe es einen kürzeren Weg, so hätte das Wasser über diesen den Knoten erreicht.

Alternativ können wir uns das Problem auch mit der Verschmelzung von Knoten vorstellen. Wir betrachten dazu unseren Startpunkt (blau) und alle von von ihm ausehenden Knoten (gestrichelt). Die rote Kante ist dabei die kleinste. Es gibt keinen kleineren Weg von unserem Startpunkt zum Knoten via der kleinsten Kante, denn jeder andere Weg wählt zum Beginn eine Kante dessen Gewicht grösser als der von uns gewählte Weg ist. Anschliessend verschmelzen wir die beiden Knoten (1,0), da wir den kürzesten Weg jetzt gefunden haben. Die Kanten von 0 können wir jetzt zu 1 hinzufügen, allerdings müssen wir noch die bereits zurückgelegte Distanz (rot) den Kanten von 0 (grün) anrechnen (daraus resultieren die rot-grünen Kanten). Nun haben wir wieder die gleiche Ausgangslage wie zu Beginn unserer Suche nur mit einem Knoten weniger. Dieses Vorgehen wiederholen wir solange, bis der ganze Graph zu einem einzigen Knoten “verschmelzt” wurde.

Ganz links die Ausgangslage, wir beginnen unsere Suche vom Knoten 1 aus. In der Mitte die Lage nach dem Zusammenfügen von Knoten 1 und 0, daraus ergeben sich neue Kanten für den Knoten 1 (rot, grün). Dies wiederholen wir solange bis nur noch ein Knoten übrig ist. Ganz rechts ist die letzte Verschmelzung der Knoten dargestellt.

Vorgehen

  • Beginn der Suche vom Startpunkt - \(S\) der Liste hinzufügen.
  • Wir nehmen den Knoten, den das Wasser als nächstes erreicht. Diesen erhalten wir aus unserer Liste.
    • Wenn das Wasser einen Knoten erreicht, leiten wir das Wasser an alle Kanten des Knoten weiter.
    • Beim Weiterleiten des Wassers, speichern wir in unserer Liste den Zeitpunkt, bei dem die Kante vollständig mit Wasser gefüllt ist und somit den Nachbarknoten erreicht.
    • Diesen Ablauf wiederholen wir solange, bis das Wasser alle Knoten erreicht hat oder das Wasser nicht mehr weiterfliessen kann.

Wir beginnen zuerst bei unserem Startknoten und füllen ihn mit Wasser (erster blauer Knoten). Anschliessend leiten wir das Wasser in die Kanten um (rot). Sobald das Wasser einen Knoten erreicht, wird die Kante blau und der Nachbarsknoten füllt sich mit Wasser. Dieser leitet ebenfalls das Wasser weiter, d.h es gibt weitere rote Kanten. Falls die rote Kante zwischen zwei blauen Knoten ist, können wir sie auch ignorieren. Das Endresultat sollte etwa wie das letzte Bild aussehen. Die blauen Kanten symbolisieren dort die kürzesten Wege.

Implementierung

Wir setzen die minimale Distanz zu allen \(n\) Knoten des Graphens auf \(\infty\), da der Computer \(\infty\) nicht speicher kann, weisen wir \(\infty\) den Wert \(-1\) zu. Dies entspricht unserem vom Wasser unberührten Zustand.

vector<int> dist(n, -1)

Wir beginnen nun unsere Suche mit unserem Startknoten \(S\) und fügen ihn unserer Liste hinzu. Dabei speichern wir auch gleich die Kürzeste Distanz vom Knoten zu sich selbst (damit wir unsere Suche beginnen können). Damit das Hinzufügen und das Auslesen aus der Liste effizient ist, verwenden wir eine Priority Queue. Der kleinste Wert muss jeweils zuvorderst sein, deswegen speichern wir alle Werte in der Priority Queue negativ ab. Der erste Wert in der Priority Queue entspricht der Distanz zum Knoten (die Zeit, welche das Wasser benötigt um ihn zu erreichen),der zweite Wert die Nummer des Knotens.

priority_queue<pair<int,int> > pq;
pq.push({0,S});
dist[start] = 0;

Nun suchen wir solange kürzeste Wege, bis das Wasser nicht mehr weiterfliessen kann. Dies ist der Fall, wenn die Priority Queue leer ist.

while( pq.size() != 0){
    // Suche nach kürzesten Wegen
}

Als erstes Lesen wir die benötigten Informationen aus der Priority Queue. \(distance\) entspricht dem Zeitpunkt, wann das Wasser den Knoten erreicht und \(pos\) dem Index des erreichten Knotens. Da wir diesen Weg jetzt betrachten, können wir ihn acuh gleich aus unserer Priority Queue löschen.

int distance = -pq.top().first;
int pos = pq.top().second;
pq.pop();

Falls der Knoten bereits vom Wasser besucht worden ist, sind alle angrenzenden Kanten bereits in unserer Priority Queue gespeichert und wir können den nächsten Zeitpunkt / Weg betrachten. Dies ist der Fall, wenn \(dist[pos]\) kleiner als \(distance\) ist. Also wenn der Zeitpunkt, wann das Wasser den Knoten erreicht bereits vergangen ist. Da \(-1\) aber unserem nicht besuchten Zustand entspricht, müssen wir diesen als Spezialfall abpassen.

if(dist[pos] != -1 && dist[pos] < distance){
    // Knoten ist bereits besucht worden
    continue;
}

Falls das Wasser den Knoten noch nicht erreicht hat, leiten wir das Wasser an alle angrenzenden Kanten weiter, welche noch nicht vom Wasser besucht worden sind und fügen sie der Priority Queue hinzu. Wir speichern für jeden Nachbarsknoten die minimale Distanz (Zeipunkt, wann Wasser den Knoten erreicht). Zusätzlich zur kürzesten Distanz könnten wir auch den ganzen Weg vom Startknoten aus speichern, indem wir jeweils den Vorgängerknoten speichern.

for(int i=0; i < (int) graph[pos].size();i++){
    // Kante aus dem Graph auslesen
    int next = graph[pos][i].first;
    int edge = graph[pos][i].second;

    if(dist[next] != -1 && dist[next] <= distance+edge){
        // Knoten bereits besucht oder bereits einen kürzeren Weg gefunden
        continue;
    }

    dist[next] = distance+edge;
    // Hier optional den Vorgänger speichern
    // pre[next] = pos;

    // Weg der Priority Queue hinzufügen
    pq.push({-(distance+edge), next});
}

Implementierung

Laufzeit- und Speicheranalsyse:

  • Jeder Knoten wird maximal einmal besucht \(O(n)\)
  • Jede Kante wird maximal einmal betrachtet, allerdings müssen sie in der Priority Queue immer sortiert sein. \(O(m \cdot log(m))\)
  • Die Gesmatlauftzeit beträgt demzufolge \(O(n + m \cdot log(m))\)
  • Jede Kante wird in der Priority Queue gespeichert \(O(m)\)
  • Zudem wird für jeden Knoten die minimale Distanz gespeichert \(O(n)\)
  • Der Gesmatspeicher beträgt demzufolge \(O(n+m)\)

Code Beispiel in C++

#include <bits/stdc++.h>

using namespace std;

// Graph als Adjazenzliste gespeichert

vector<int> dijkstra(int start, vector<vector<pair<int,int> > > &graph){
    int n = (int)graph.size();
    priority_queue<pair<int,int> > pq;
    vector<int> dist(n,-1);
    pq.push({0,start});
    dist[start] = 0;

    while(pq.size() != 0){
        int distance = -pq.top().first;
        int pos = pq.top().second;
        pq.pop();

        if(dist[pos] != -1 && dist[pos] < distance){
            continue;
        }

        for(int i=0; i < (int) graph[pos].size();i++){
            int next = graph[pos][i].first;
            int edge = graph[pos][i].second;

            if(dist[next] != -1 && dist[next] <= distance+edge){
                continue;
            }

            dist[next] = distance+edge;

            pq.push({-(distance+edge), next});
        }
    }

    return dist;
}