ZU DEN KURSEN!

Operations Research - Fifo-Algorithmus

Kursangebot | Operations Research | Fifo-Algorithmus

Operations Research

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 $n$ Knoten und einem Startknoten. Es werden alle kürzesten Wege zwischen dem Startknoten und allen anderen Knoten gesucht.

Methode

Hier klicken zum Ausklappen

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] =

$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} 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.

FIFO-Algorithmus

Beispiel

Hier klicken zum Ausklappen

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$     $

$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

Hier klicken zum Ausklappen

Die Schlange ergibt sich also zu $

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}

$120

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

$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

Hier klicken zum Ausklappen

$


Knoten 3:

Für den Knoten 3 gilt dieselbe Vorgehensweise:

$D(1) + k_{13} = 0 + 30 = 30

$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

Hier klicken zum Ausklappen

$

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$             xx

Die Schlange $

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(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

Hier klicken zum Ausklappen

$

Der Knoten 2 wird aus der Schlange entfernt:

Methode

Hier klicken zum Ausklappen

$


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$             xxx
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

$D(4) = 130$.

$V(4) = 3$.

$SE = 4$:

Methode

Hier klicken zum Ausklappen

 $

Es wird der Knoten 3 aus der Schlange entfernt:

Methode

Hier klicken zum Ausklappen

 $

Knoten 5:

$D(3) + k_{35} = 30 + 45 = 75

$D(5) = 75$.

$V(5) = 3$.

$SE = 5$:

Methode

Hier klicken zum Ausklappen

$

Am Ende wird der Knoten 3 aus der Schlange entfernt:

Methode

Hier klicken zum Ausklappen

$


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$              xxxx
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

$D(6) = 170$.

$V(6) = 4$.

$SE = 6$:

Methode

Hier klicken zum Ausklappen

$

Am Ende wird der Knoten 4 aus der Schlange entfernt:

Methode

Hier klicken zum Ausklappen

$


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$             xxxxx

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

$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

$D(6) = 115$.

$V(6) = 5$.

$SE = 6$:

Methode

Hier klicken zum Ausklappen

$

Am Ende wird der Knoten 5 aus der Schlange entfernt:

Methode

Hier klicken zum Ausklappen

$


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$              xxxxxx
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

Hier klicken zum Ausklappen

 $

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.