Graphenalgorithmen

Floyd-Warshall-Algorithmus

 aufwärts

Problem

Gegeben sei ein gerichteter Graph G = (V, E) mit  V = {0, ..., n-1}, n Element natürliche Zahlen. Gefragt ist für alle Paare von Knoten (ij), ob es in G einen Weg von i nach j gibt.

Der Algorithmus von Warshall [War 62] berechnet als Ergebnis einen Graphen G+ = (V, E+), der genau dann eine Kante (ij) enthält, wenn es in G einen Weg von i nach j gibt. Der Graph G+ heißt transitive Hülle von G, da seine Kantenrelation E+ die kleinste transitive Relation ist, die E umfasst.

Bild 1 zeigt als Beispiel einen Graphen G. Die transitive Hülle G+ von G enthält zusätzliche Kanten, so beispielsweise die Kante (3,1), weil es in G einen Weg von 3 nach 1 gibt. Alle auf diese Weise hinzukommenden Kanten von G+ werden weiter unten in einer Simulation berechnet.

Bild 1: Graph G und transitive Hülle G+
Bild 1: Graph G und transitive Hülle G+

Idee

Der Graph G+ wird aus G entwickelt, indem schrittweise neue Kanten hinzugenommen werden. In Schritt 0 kommt eine Kante (ij) hinzu, wenn sich aus zwei Kanten ein Weg von i nach j bilden lässt, der über den Knoten 0 führt (d.h. wenn (i, 0) und (0, j) Kanten sind). In Schritt 1 kommt eine Kante (ij) hinzu, wenn sich aus zwei Kanten ein Weg von i nach j bilden lässt, der über den Knoten 1 führt; hierbei werden die in Schritt 0 neu gefundenen Kanten mit berücksichtigt. Dieses Verfahren wird bis zum Knoten n-1 fortgesetzt.

In jedem Schritt k entsprechen die bis dahin gefundenen Kanten den Wegen, deren innere Knoten alle kleiner gleichk sind. Damit repräsentieren die in Schritt n-1 bis dahin gefundenen Kanten alle Wege (Beweis durch vollständige Induktion).

 

Warshall-Algorithmus
Eingabe:Graph G mit V = {0, ..., n-1}
Ausgabe:Graph G+
Methode:
  1. für Knoten k = 0, ..., n-1 wiederhole
    1. für alle Paare von Knoten (i, j) wiederhole
      1. wenn (i, k) und (k, j) Kanten sind dann
        1. erzeuge Kante (i, j)

 

Im folgenden Beispiel werden die in jedem Schritt neu hinzu kommenden Kanten durch unterschiedliche Farben gekennzeichnet:

Beispiel:  

(Applet zur Simulation des Warshall-Algorithmus)

Implementierung

Es gibt unterschiedliche Möglichkeiten, einen Graphen als Datenstruktur zu repräsentieren. Eine einfache Möglichkeit besteht darin, die Kanten des Graphen in Form einer Adjazenzmatrix darzustellen.

Definition:  Sei G = (V, E) ein Graph mit  V = {0, ..., n-1},  n Element natürliche Zahlen. Die Adjazenzmatrix des Graphen ist eine boolesche n × n-Matrix A, für die gilt

Ai,j =  geschweifte Klammer
true        falls (i, j) eine Kante ist, d.h. falls (i, jElement E
false    sonst

für alle  i, j Element V.

Beispiel:  Adjazenzmatrix des Graphen G aus Bild 1   (leere Einträge = false, 1 = true)

    01234
0 11  
1  1  
21    
31    
4     

Die Implementierung des Warshall-Algorithmus entwickelt aus der Adjazenzmatrix A des Graphen G schrittweise die Adjazenzmatrix A+ der transitiven Hülle G+ des Graphen.

 

Algorithmus warshall
Eingabe:n × n-Adjazenzmatrix A eines Graphen G
Ausgabe:n × n-Adjazenzmatrix A+ des Graphen G+ mit A+i,j = true, falls es einen Weg von Knoten i nach Knoten j gibt und A+i,j = false sonst
Methode:
  1. for (k=0; k<n; k++)
       for (i=0; i<n; i++)
          for (j=0; j<n; j++)
             a[i][j]=a[i][j] || a[i][k] && a[k][j]
    

 

Wichtig ist die Reihenfolge der Schleifen: Die k-Schleife muss die äußere Schleife sein.

Kürzeste Wege

Gegeben sei ein Graph G = (V, E) mit V = {0, ..., n-1},  n Element natürliche Zahlen. Der Algorithmus von Floyd [Flo 62] berechnet für alle Paare von Knoten (i, j) die Länge des kürzesten Weges von i nach j. Der Algorithmus hat dieselbe Struktur wie der Warshall-Algorithmus. Statt der Operationen || (Oder) und && (Und) werden die Operationen min und + verwendet. Statt der Adjazenzmatrix wird eine Matrix A eingegeben, wobei

Ai,j =  geschweifte Klammer
1        falls (i, jElement E
unendlich    sonst

 

 

Algorithmus floyd
Eingabe:n × n-Matrix A mit  Ai,j = 1   falls (i, jElement E  und Ai,j = unendlich   sonst
Ausgabe:n × n-Matrix A mit  Ai,j = d  falls der kürzeste Weg von Knoten i nach Knoten j die Länge d hat und  Ai,j = unendlich  falls es keinen Weg von i nach j gibt
Methode:
  1. for (k=0; k<n; k++)
       for (i=0; i<n; i++)
          for (j=0; j<n; j++)
             a[i][j]=min(a[i][j], a[i][k]+a[k][j])
    

 

Der Beweis des Floyd-Algorithmus folgt analog dem Beweis des Warshall-Algorithmus. Der Algorithmus funktioniert auch mit beliebigen, nichtnegativen Kantengewichten.

Der Floyd-Algorithmus berechnet in dieser Form nur die Länge des kürzesten Weges. Um den kürzesten Weg selbst zu konstruieren, wird parallel zu A eine weitere Matrix F geführt, in der als Eintrag Fi,j jeweils der erste Knoten auf dem kürzesten Weg von i nach j steht. Jedesmal, wenn der Floyd-Algorithmus einen kürzeren Weg von i nach j als den bisher bekannten findet, wird Fi,j aktualisiert.

Transitive Hülle und kürzeste Wege sind Spezialfälle des sogenannten algebraischen Pfadproblems [AHU 74][CLRS 01][Lan 88].

Literatur

Originalartikel:

[Flo 62]R.W. Floyd: Algorithm 97: Shortest Path. Communications of the ACM, 5, 6, 345 (1962)
[War 62]S. Warshall: A Theorem on Boolean Matrices. Journal of the ACM, Vol. 9, 1, 11-12 (1962)

 

Die algebraischen Grundlagen für die Lösung von Pfadproblemen in Graphen finden sich in [AHU 74] und in [CLRS 01]. Eine parallele Implementation des Warshall-Algorithmus und eines Algorithmus zur Lösung des algebraischen Pfadproblems ist in [Lan 88] bzw. unter [1] angegeben.

[AHU 74]A.V. Aho, J.E. Hopcroft, J.D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley (1974)
[CLRS 01]T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: Introduction to Algorithms. 2. Auflage, The MIT Press (2001)
[Lan 88]H.W. Lang: Transitive Closure on the Instruction Systolic Array. In: K. Bromley, S.Y. Kung, E. Swartzlander (eds.): Proceedings of the Int. Conf. on Systolic Arrays, San Diego, Computer Society Press, Washington D.C., 295-304 (1988)
[Web 1]http://www.inf.fh-flensburg.de/lang/papers/trans/transcl.htm  

 

Weiter mit:   [Minimaler Spannbaum]   [Literatur]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 29.01.1998   Updated: 20.05.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik