Fifo-Algorithmus

In diesem Abschnitt wird der FIFO-Algorithmus zur Bestimmung von kürzesten Wegen in Graphen ausführlich behandelt.

Gegeben sei ein Diagraph mit Knoten und einem Startknoten. Es werden alle kürzesten Wege zwischen dem Startknoten und allen anderen Knoten gesucht.

Die Vorgehensweise soll im Folgenden anhand eines Beispiels demonstriert werden.

Begonnen wird mit der Initialisierung:

Als Startknoten wird der Knoten 1 gewählt:

,

für die Knoten ,

für alle Knoten .

Das Ganze wird in eine Tabelle eingetragen:

In der obigen Tabelle ist die Initialisierung eingetragen. Dabei wurde als Startknoten der Knoten 1 gewählt. Dem Startknoten 1 wird zugeordnet, allen anderen Knoten . ist zunächst für alle Knoten leer. Der Anfangszeiger und der Endzeiger sind bei der Initialisierung gleich dem Startknoten 1.

Hierbei ist der 1. Wert immer der Anfangszeiger und der 2. Wert immer der Endzeiger . Es wird zusätzlich eine Schlange aufgestellt, welche alle Anfangszeiger berücksichtigt: .

1. Iteration

Es werden nun alle Nachfolger vom Anfangszeiger betrachtet. In diesem Fall ist und die Nachfolger:

. 

Knoten 2:

Es wird dann der kürzeste Weg des Startknotens zur Pfeilbewertung des Nachfolgerknotens 2 addiert:

. 

Das Ergebnis wird mit dem kürzesten Weg des Nachfolgerknotens verglichen:

.

Ist das Ergebnis (hier: 120) kleiner als der kürzeste Weg des Nachfolgerknotens (hier: ) so wird der kürzeste Weg des Nachfolgerknotens gleich dem Ergebnis gesetzt.

Es gilt also und demnach wird gesetzt. Der Vorgänger von Knoten ist demnach Knoten :

.

Es gilt außerdem, dass Knoten 2 noch nicht in vorhanden ist und demnach als Endzeiger in die Schlange aufgenommen . Der Knoten wird aus der Schlange entfernt:

Knoten 3:

Für den Knoten 3 gilt dieselbe Vorgehensweise:

.

.

Knoten 3 ist noch nicht in vorhanden  und wird demnach als Endzeiger in die Schlange aufgenommen . Der Knoten wird aus der Schlange entfernt:

Es gilt jetzt (alle Knoten die bereits waren).

Die neue Tabelle ergibt sich zu:

Die Schlange bedeutet, dass nach dem Knoten 2 der Knoten 3 folgt. Demnach wird bei Knoten 2 unter der Knoten 3 eingetragen.

2. Iteration

Es werden nun alle Nachfolger vom Anfangszeiger betrachtet. In diesem Fall ist . Der Nachfolger von Knoten 2 ist:

. 

Knoten 3:

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 .

.

Der Knoten 2 wird aus der Schlange entfernt:

Die neue Tabelle ergibt sich zu:

3. Iteration

Es werden nun alle Nachfolger vom Anfangszeiger betrachtet. In diesem Fall ist . Die Nachfolger von Knoten 3 sind:

. 

Knoten 4:

.

.

:

Es wird der Knoten 3 aus der Schlange entfernt:

Knoten 5:

.

.

:

Am Ende wird der Knoten 3 aus der Schlange entfernt:

Die neue Tabelle ergibt sich zu:

4. Iteration

Es werden nun alle Nachfolger vom Anfangszeiger betrachtet. In diesem Fall ist . Die Nachfolger von Knoten 4 sind:

. 

Knoten 2:

Es wird keine Änderung vorgenommen, da der vorhande Weg kürzer ist. Der Vorgänger bleibt also Knoten 1.

Da Knoten 2 bereits war (siehe Tabelle unterste Zeile)), wird dieser nicht mehr in die Schlange aufgenommen.

Knoten 6:

.

.

:

Am Ende wird der Knoten 4 aus der Schlange entfernt:

Die neue Tabelle ergibt sich zu:

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 betrachtet. In diesem Fall ist . Die Nachfolger von Knoten 5 sind:

. 

Knoten 4:

Knoten 4 war bereits (siehe unterste Zeile der Tabelle) und wird nicht in die Schlange aufgenommen.

Knoten 6:

.

.

:

Am Ende wird der Knoten 5 aus der Schlange entfernt:

Die Tabelle ergibt sich wie folgt:

6. Iteration

Es werden nun alle Nachfolger vom Anfangszeiger betrachtet. In diesem Fall ist . Der Nachfolger von Knoten 6 ist:

. 

Knoten 4:

 Es wird keine Änderung vorgenommen, da der vorhande Weg kürzer ist. Der Vorgänger bleibt also Knoten 5.

Der Knoten 4 ist bereist (siehe unterste Zeile der Tabelle) wird demnach nicht aufgenommen:

Es gilt 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:

Der Knoten 4 hat als Vorgänger Knoten 5, dieser hat als Vorgänger Knoten 3 und dieser hat als Vorgänger Knoten 1.