Dijkstra

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

Laufzeit- und Speicheranalyse:

• Die Grösse der Priority Queue ist maximal $m$, da jede Kante nie mehr als einmal besichtigt wird. Für eine Priority Queue mit Grösse $m$ ist die Laufzeit, um das Minimum zu entfernen $O(\log(m))$. Die Laufzeit um einen Wert einzufügen ist ebenfalls $O(\log(m))$.
• Jeder Knoten wird maximal einmal besucht und dabei von der Priority Queue entfernt, das braucht $O(n \cdot \log(m))$
• Jede Kante wird maximal einmal betrachtet, dabei wird maximal ein neuer Wert in die Priority Queue eingefügt: $O(m \cdot \log(m))$
• Die Gesamtlauftzeit 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 Gesamtspeicher 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;
}

int dijkstra(int start, int finish, vector<vector<pair<int, int>>>& g){
    int n = (int)g.size();
    vector<int> dist(n, -1);
    priority_queue<pair<int, int>>pq;
    pq.push({0, start});
    while(!pq.empty()){
        int d = -pq.top().first;  //kürzeste Distanz momentan
        int u = pq.top().second;  //Der dazugehörige Knoten
        pq.pop();

        if(dist[u] != -1)continue;  //Falls der Knoten schon besucht wurde, existiert einen kürzeren Pfad
        dist[u] = d;   //d ist die kürzeste Distanz zu u

        for(auto [v, w] : g[u]){
            pq.push({-(dist[u] + w), v});  //Neue Distanzen werden hinzugefügt
        }
    }
    return dist[finish];
}

// invariant: not visited <=> dist[i]=-1
vector<int> dist(n, -1);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.emplace(0, start);
while (!pq.empty()) {
    auto [d, v] = pq.top();
    pq.pop();
    if (dist[v] != -1) continue;
    dist[v] = d;
    for (auto [u, cost] : g[v])
        pq.emplace(d + cost, u);
}

 // assume a weighted graph in:  vector<vector<array<int, 2>>> adj(n);

 vector<int64_t> dist(n, -1);  // dist only updated after visiting

 priority_queue<array<int64_t, 2>> pq;
 pq.push({0, start});
 while (pq.size() > 0) {
     auto [d, v] = pq.top(); pq.pop();  // largest negative is smallest positive
     if (dist[v] != -1) continue;  // skip already processed vertices
     dist[v] = -d;  // remember we stored negative distances

     for (auto [u, w]: adj[v]) pq.push({-dist[v] - w, u});  // negative distances!
 }