Graphenalgorithmen

Problem

Gegeben sei ein gerichteter Graph G = (V, E) mit  V = {0, ..., n-1}, n ∈ ℕ. Gefragt ist für alle Paare von Knoten (i, j), 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 (i, j) 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 Kanten­relation 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 beispiels­weise die Kante (3,1), weil es in G einen Weg von 3 nach 1 gibt. Alle auf diese Weise hinzu­kommenden Kanten von G⁺ werden weiter unten in einer Simulation berechnet.

Idee

Der Graph G⁺ wird aus G entwickelt, indem schrittweise neue Kanten hinzu­genommen werden. In Schritt 0 kommt eine Kante (i, j) 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 (i, j) 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ück­sichtigt. 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  ≤ k 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)

Implementierung

Es gibt unterschiedliche Möglich­keiten, einen Graphen als Daten­struktur zu repräsentieren. Eine einfache Möglichkeit besteht darin, die Kanten des Graphen in Form einer Adjazenz­matrix darzustellen.

Definition:  Sei G = (V, E) ein Graph mit  V = {0, ..., n-1},  n ∈ ℕ. Die Adjazenz­matrix des Graphen ist eine boolesche n × n-Matrix A, für die gilt

Ai,j =

true         falls (i, j) eine Kante ist, d.h. falls (i, j) ∈ E false     sonst

für alle  i, j ∈ V.

Die Implementierung des Warshall-Algorithmus entwickelt aus der Adjazenz­matrix A des Graphen G schrittweise die Adjazenz­matrix 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 ∈ ℕ. 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 Adjazenz­matrix wird eine Matrix A eingegeben, wobei

Ai,j =

1         falls (i, j) ∈ E ∞     sonst

Algorithmus floyd

Eingabe:

n × n-Matrix A mit  A_i,j = 1   falls (i, j) ∈ E  und A_i,j = ∞   sonst

Ausgabe:

n × n-Matrix A mit  A_i,j = d  falls der kürzeste Weg von Knoten i nach Knoten j die Länge d hat und  A_i,j = ∞  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, nicht­negativen Kanten­gewichten.

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 F_i,j jeweils der erste Knoten auf dem kürzesten Weg von i nach j steht. Jedes Mal, wenn der Floyd-Algorithmus einen kürzeren Weg von i nach j als den bisher bekannten findet, wird F_i,j aktualisiert.

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

Literatur

Original­artikel:

[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://hwlang.de/papers/trans/transcl.htm