In diesem Abschnitt wird der FIFO-Algorithmus zur Bestimmung von kürzesten Wegen in Graphen ausführlich behandelt.
Gegeben sei ein Diagraph mit $n$ Knoten und einem Startknoten. Es werden alle kürzesten Wege zwischen dem Startknoten und allen anderen Knoten gesucht.
Methode
FIFO-Algorithmus
Gegeben sei ein Diagraph mit $n$ Knoten und einem Startknoten $a$. Alle Pfeile seien mit $k(i,j)$ bewertet. Gesucht wird der kürzeste Weg zwischen dem Startknoten und allen anderen Knoten des Diagraphen.
Sei $D(i)$ die kürzeste Entfernung vom Startknoten $a$ zum Knoten $i$, $V(i)$ der unmittelbare Vorgänger von Knoten $i$ auf dem kürzesten Weg vom Startknoten $a$ zum Knoten $i$ und die Menge $S[i]$ die Speicherung der Menge der markierten Knoten als Warteschlange, wobei $SK$ der Anfangszeiger der Warteschlange darstellt und $SE$ der Endzeiger der Warteschlange.
Initialisierung:
$S[i] = < SK, SE]$ mit $SK = SE = a$
$D(a) = 0$ und $D(i) = \infty$ für alle Knoten $i \neq a$.
$V(i) = - $ für alle Knoten $i$.
Iteration:
1. Schritt: Auswahl des Knotens $K = SK$.
2. Schritt: Es wird nun jeder Nachfolger $j$ vom Knoten $K = SK$ separat betrachtet und folgende Berechnung durchgeführt: $D(K) + k_{K;j} < D(j)$, so wird $D(j) = D(K) + k_{Kj}, V(j) = K$ gesetzt. Danach wird der Nachfolgerknoten $SE = j$ gesetzt, sofern dieser nicht bereits in $S$ enthalten ist. Der Knoten $K$ wird dabei in $S$ aufgenommen und aus der Warteschlange $S[i]$ entfernt.
Die Schritte 1-2 werden so lange wiederholt bis gilt $SK = SE$.
Die Vorgehensweise soll im Folgenden anhand eines Beispiels demonstriert werden.
Beispiel
Gegeben sei der obige Diagraph. Für diesen soll nach dem FIFO-Algorithmus der kürzeste Weg von einem Startknoten zu allen anderen Knoten bestimmt werden.
Begonnen wird mit der Initialisierung:
Als Startknoten wird der Knoten 1 gewählt:
$SK := SE := 1$ $<1,1]$
$D(1) = 0$,
$D(i) = \infty$ für die Knoten $i = 2,3,4,5,6$,
$V(i) = -$ für alle Knoten $i = 1,2,3,4,5,6$.
Das Ganze wird in eine Tabelle eingetragen:
| $i$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ |
| $D(i)$ | $0$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ |
| $V(i)$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$ |
| $S[i]$ | $1$ | |||||
| $S$ | x |
In der obigen Tabelle ist die Initialisierung eingetragen. Dabei wurde als Startknoten der Knoten 1 gewählt. Dem Startknoten 1 wird $D(1) = 0$ zugeordnet, allen anderen Knoten $D(i) = \infty$. $V(i)$ ist zunächst für alle Knoten leer. Der Anfangszeiger $SK$ und der Endzeiger $SE$ sind bei der Initialisierung gleich dem Startknoten 1.
Methode
Die Schlange ergibt sich also zu $< 1,1]$.
Hierbei ist der 1. Wert immer der Anfangszeiger $SK$ und der 2. Wert immer der Endzeiger $SE$. Es wird zusätzlich eine Schlange $S$ aufgestellt, welche alle Anfangszeiger berücksichtigt: $S = (1)$.
1. Iteration
Es werden nun alle Nachfolger vom Anfangszeiger $SK$ betrachtet. In diesem Fall ist $SK = 1$ und die Nachfolger:
$j = 2,3$.
Knoten 2:
Es wird dann der kürzeste Weg des Startknotens $D(1) = 0$ zur Pfeilbewertung des Nachfolgerknotens 2 addiert:
$D(1) + k_{12} = 0 + 120 = 120$.
Das Ergebnis wird mit dem kürzesten Weg des Nachfolgerknotens $D(2) = \infty$ verglichen:
$D(1) + k_{12} < D(2)$
$120 < \infty$.
Ist das Ergebnis (hier: 120) kleiner als der kürzeste Weg des Nachfolgerknotens (hier: $\infty$) so wird der kürzeste Weg des Nachfolgerknotens gleich dem Ergebnis gesetzt.
Es gilt also $120 < \infty$ und demnach wird $D(2) = 120$ gesetzt. Der Vorgänger von Knoten $2$ ist demnach Knoten $1$:
$V(2) = 1$.
Es gilt außerdem, dass Knoten 2 noch nicht in $S$ vorhanden ist und demnach als Endzeiger in die Schlange aufgenommen $SE = 2$. Der Knoten $SK = 1$ wird aus der Schlange entfernt:
Methode
$< 1,2]$
Knoten 3:
Für den Knoten 3 gilt dieselbe Vorgehensweise:
$D(1) + k_{13} = 0 + 30 = 30 < \infty$
$D(3) = 30$.
$V(3) = 1$.
Knoten 3 ist noch nicht in $S$ vorhanden und wird demnach als Endzeiger in die Schlange aufgenommen $SE = 3$. Der Knoten $SK = 1$ wird aus der Schlange entfernt:
Methode
$< 2,3]$
Es gilt jetzt $S = (1,2)$ (alle Knoten die bereits $SK$ waren).
Die neue Tabelle ergibt sich zu:
| $i$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ |
| $D(i)$ | $0$ | $120$ | $30$ | $\infty$ | $\infty$ | $\infty$ |
| $V(i)$ | $-$ | $1$ | $1$ | $-$ | $-$ | $-$ |
| $S[i]$ | $3$ | |||||
| $S$ | x | x |
Die Schlange $<2,3$ bedeutet, dass nach dem Knoten 2 der Knoten 3 folgt. Demnach wird bei Knoten 2 unter $S[i]$ der Knoten 3 eingetragen.
2. Iteration
Es werden nun alle Nachfolger vom Anfangszeiger $SK$ betrachtet. In diesem Fall ist $SK = 2$. Der Nachfolger von Knoten 2 ist:
$j = 3$.
Knoten 3:
$D(2) + k_{23} < D(3)$
$D(2) + k_{23} = 120 + 35 = 155 > 30$
Da hier der Weg von Knoten 2 zu Knoten 3 länger ist als (155) als der bereits festgelegte Wert (30) wird in diesem Fall nichts verändert. Der Vorgänger bleibt der Knoten 1 mit $D(3) = 30$.
$V(3) = 1$
$SE = 3$.
Methode
$< 2,3,3]$
Der Knoten 2 wird aus der Schlange entfernt:
Methode
$< 3,3]$
Die neue Tabelle ergibt sich zu:
| $i$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ |
| $D(i)$ | $0$ | $120$ | $30$ | $\infty$ | $\infty$ | $\infty$ |
| $V(i)$ | $-$ | $1$ | $1$ | $-$ | $-$ | $-$ |
| $S[i]$ | $3$ | |||||
| $S$ | x | x | x |
3. Iteration
Es werden nun alle Nachfolger vom Anfangszeiger $SK$ betrachtet. In diesem Fall ist $SK = 3$. Die Nachfolger von Knoten 3 sind:
$j = 4,5$.
Knoten 4:
$D(3) + k_{34} = 30 + 100 = 130 < \infty$
$D(4) = 130$.
$V(4) = 3$.
$SE = 4$:
Methode
$<3,3,4]$
Es wird der Knoten 3 aus der Schlange entfernt:
Methode
$<3,4]$
Knoten 5:
$D(3) + k_{35} = 30 + 45 = 75 < \infty$
$D(5) = 75$.
$V(5) = 3$.
$SE = 5$:
Methode
$<3,4,5]$
Am Ende wird der Knoten 3 aus der Schlange entfernt:
Methode
$<4,5]$
Die neue Tabelle ergibt sich zu:
| $i$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ |
| $D(i)$ | $0$ | $120$ | $30$ | $130$ | $75$ | $\infty$ |
| $V(i)$ | $-$ | $1$ | $1$ | $3$ | $3$ | $-$ |
| $S[i]$ | $5$ | |||||
| $S$ | x | x | x | x |
4. Iteration
Es werden nun alle Nachfolger vom Anfangszeiger $SK$ betrachtet. In diesem Fall ist $SK = 4$. Die Nachfolger von Knoten 4 sind:
$j = 2,6$.
Knoten 2:
$D(4) + k_{42} = 130 + 80 = 210 > 120$ Es wird keine Änderung vorgenommen, da der vorhande Weg kürzer ist. Der Vorgänger bleibt also Knoten 1.
Da Knoten 2 bereits $SK$ war (siehe Tabelle unterste Zeile)), wird dieser nicht mehr in die Schlange aufgenommen.
Knoten 6:
$D(4) + k_{46} = 130 + 40 = 170 < \infty$
$D(6) = 170$.
$V(6) = 4$.
$SE = 6$:
Methode
$<4,5,6]$
Am Ende wird der Knoten 4 aus der Schlange entfernt:
Methode
$<5,6]$
Die neue Tabelle ergibt sich zu:
| $i$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ |
| $D(i)$ | $0$ | $120$ | $30$ | $130$ | $75$ | $170$ |
| $V(i)$ | $-$ | $1$ | $1$ | $3$ | $3$ | $4$ |
| $S[i]$ | $6$ | |||||
| $S$ | x | x | x | x | x |
Die Schlange wird wir folgt eingetragen: Knoten 5 hat als Nachfolger der Schlange den Knoten 6. Knoten 6 ist das Ende der Schlange und hat keinen Nachfolger.
5. Iteration
Es werden nun alle Nachfolger vom Anfangszeiger $SK$ betrachtet. In diesem Fall ist $SK = 5$. Die Nachfolger von Knoten 5 sind:
$j = 4,6$.
Knoten 4:
$D(5) + k_{54} = 75 + 35 = 110 < 130$
$D(4) = 110$
$V(4) = 5$
Knoten 4 war bereits $SK$ (siehe unterste Zeile der Tabelle) und wird nicht in die Schlange aufgenommen.
Knoten 6:
$D(5) + k_{56} = 75 + 40 = 115 < 170$
$D(6) = 115$.
$V(6) = 5$.
$SE = 6$:
Methode
$<5,6,6]$
Am Ende wird der Knoten 5 aus der Schlange entfernt:
Methode
$<6,6]$
Die Tabelle ergibt sich wie folgt:
| $i$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ |
| $D(i)$ | $0$ | $120$ | $30$ | $110$ | $75$ | $115$ |
| $V(i)$ | $-$ | $1$ | $1$ | $5$ | $3$ | $5$ |
| $S[i]$ | $6$ | |||||
| $S$ | x | x | x | x | x | x |
6. Iteration
Es werden nun alle Nachfolger vom Anfangszeiger $SK$ betrachtet. In diesem Fall ist $SK = 6$. Der Nachfolger von Knoten 6 ist:
$j = 4$.
Knoten 4:
$D(6) + k_{64} = 115 + 35 = 150 > 110$ Es wird keine Änderung vorgenommen, da der vorhande Weg kürzer ist. Der Vorgänger bleibt also Knoten 5.
Der Knoten 4 ist bereist $SK$ (siehe unterste Zeile der Tabelle) wird demnach nicht aufgenommen:
Methode
$< 6]$
Es gilt $SK = SE$ und demnach wird das Verfahren hier abgebrochen! Der kürzeste Weg wurde bestimmt.
Kürzester Weg
Es kann nun der kürzeste Weg vom Startknoten aus zu den einzelnen Knoten aus der Tabelle abgelesen werden. Wird zum Beispiel der Weg zum Knoten 4 gesucht, so muss man die Tabelle rückwärts lesen:
$4 - 5 - 3 - 1$
Der Knoten 4 hat als Vorgänger Knoten 5, dieser hat als Vorgänger Knoten 3 und dieser hat als Vorgänger Knoten 1.
Weitere interessante Inhalte zum Thema
-
Dijkstra-Algorithmus
Vielleicht ist für Sie auch das Thema Dijkstra-Algorithmus (Greedy-Algorithmus) aus unserem Online-Kurs Operations Research 1 interessant.
