Embed Size (px)
Citation preview
Der Floyd-Warshall-Algorithmus
Beispiel
Als nächstes betrachten wir folgenden Digraphen:
1
2
5 4
32
−2
10
−3
1
43
d0 1 2 3 4 5
1 ∞ 2 ∞ ∞ ∞
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ ∞
4 ∞ ∞ 4 ∞ ∞
5 10 ∞ 3 1 ∞
d1 1 2 3 4 5
1
2
3
4
5
Der Floyd-Warshall-Algorithmus
Beispiel
Als nächstes betrachten wir folgenden Digraphen:
1
2
5 4
32
−2
10
−3
1
43
d0 1 2 3 4 5
1 ∞ 2 ∞ ∞ ∞
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ ∞
4 ∞ ∞ 4 ∞ ∞
5 10 ∞ 3 1 ∞
d1 1 2 3 4 5
1
2
3
4
5
Der Floyd-Warshall-Algorithmus
Beispiel
Als nächstes betrachten wir folgenden Digraphen:
1
2
5 4
32
−2
10
−3
1
43
d0 1 2 3 4 5
1 ∞ 2 ∞ ∞ ∞
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ ∞
4 ∞ ∞ 4 ∞ ∞
5 10 ∞ 3 1 ∞
d1 1 2 3 4 5
1
2
3
4
5
Der Floyd-Warshall-Algorithmus
Beispiel
Als nächstes betrachten wir folgenden Digraphen:
1
2
5 4
32
−2
10
−3
1
43
d0 1 2 3 4 5
1 ∞ 2 ∞ ∞ ∞
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ ∞
4 ∞ ∞ 4 ∞ ∞
5 10 ∞ 3 1 ∞
d1 1 2 3 4 5
1 ∞ 2 ∞ ∞ ∞
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ ∞
4 ∞ ∞ 4 ∞ ∞
5 10 3 1 ∞
Der Floyd-Warshall-Algorithmus
Beispiel
Als nächstes betrachten wir folgenden Digraphen:
1
2
5 4
32
−2
10
−3
1
43
d0 1 2 3 4 5
1 ∞ 2 ∞ ∞ ∞
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ ∞
4 ∞ ∞ 4 ∞ ∞
5 10 ∞ 3 1 ∞
d1 1 2 3 4 5
1 ∞ 2 ∞ ∞ ∞
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ ∞
4 ∞ ∞ 4 ∞ ∞
5 10 12 3 1 ∞
Der Floyd-Warshall-Algorithmus
Beispiel
Als nächstes betrachten wir folgenden Digraphen:
1
2
5 4
32
−2
10
−3
1
43
d1 1 2 3 4 5
1 ∞ 2 ∞ ∞ ∞
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ ∞
4 ∞ ∞ 4 ∞ ∞
5 10 12 3 1 ∞
d2 1 2 3 4 5
1
2
3
4
5
Der Floyd-Warshall-Algorithmus
Beispiel
Als nächstes betrachten wir folgenden Digraphen:
1
2
5 4
32
−2
10
−3
1
43
d2 1 2 3 4 5
1 ∞ 2 ∞ ∞ ∞
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ ∞
4 ∞ ∞ 4 ∞ ∞
5 10 12 3 1 ∞
d2 1 2 3 4 5
1
2
3
4
5
Der Floyd-Warshall-Algorithmus
Beispiel
Als nächstes betrachten wir folgenden Digraphen:
1
2
5 4
32
−2
10
−3
1
43
d2 1 2 3 4 5
1 ∞ 2 ∞ ∞ ∞
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ ∞
4 ∞ ∞ 4 ∞ ∞
5 10 12 3 1 ∞
d2 1 2 3 4 5
1
2
3
4
5
Der Floyd-Warshall-Algorithmus
Beispiel
Als nächstes betrachten wir folgenden Digraphen:
1
2
5 4
32
−2
10
−3
1
43
d2 1 2 3 4 5
1 ∞ 2 ∞ ∞ ∞
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ ∞
4 ∞ ∞ 4 ∞ ∞
5 10 12 3 1 ∞
d2 1 2 3 4 5
1 ∞ 2 ∞ ∞
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞
4 ∞ ∞ 4 ∞ ∞
5 10 12 3 1
Der Floyd-Warshall-Algorithmus
Beispiel
Als nächstes betrachten wir folgenden Digraphen:
1
2
5 4
32
−2
10
−3
1
43
d2 1 2 3 4 5
1 ∞ 2 ∞ ∞ ∞
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ ∞
4 ∞ ∞ 4 ∞ ∞
5 10 12 3 1 ∞
d2 1 2 3 4 5
1 ∞ 2 ∞ ∞ −1
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ −5
4 ∞ ∞ 4 ∞ ∞
5 10 12 3 1 9
Der Floyd-Warshall-Algorithmus
Beispiel
Als nächstes betrachten wir folgenden Digraphen:
1
2
5 4
32
−2
10
−3
1
43
d2 1 2 3 4 5
1 ∞ 2 ∞ ∞ −1
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ −5
4 ∞ ∞ 4 ∞ ∞
5 10 12 3 1 9
d3 1 2 3 4 5
1
2
3
4
5
Der Floyd-Warshall-Algorithmus
Beispiel
Als nächstes betrachten wir folgenden Digraphen:
1
2
5 4
32
−2
10
−3
1
43
d2 1 2 3 4 5
1 ∞ 2 ∞ ∞ −1
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ −5
4 ∞ ∞ 4 ∞ ∞
5 10 12 3 1 9
d3 1 2 3 4 5
1
2
3
4
5
Der Floyd-Warshall-Algorithmus
Beispiel
Als nächstes betrachten wir folgenden Digraphen:
1
2
5 4
32
−2
10
−3
1
43
d2 1 2 3 4 5
1 ∞ 2 ∞ ∞ −1
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ −5
4 ∞ ∞ 4 ∞ ∞
5 10 12 3 1 9
d3 1 2 3 4 5
1
2
3
4
5
Der Floyd-Warshall-Algorithmus
Beispiel
Als nächstes betrachten wir folgenden Digraphen:
1
2
5 4
32
−2
10
−3
1
43
d2 1 2 3 4 5
1 ∞ 2 ∞ ∞ −1
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ −5
4 ∞ ∞ 4 ∞ ∞
5 10 12 3 1 9
d3 1 2 3 4 5
1 ∞ 2 ∞ ∞ −1
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ −5
4 ∞ 4 ∞
5 10 3 1
Der Floyd-Warshall-Algorithmus
Beispiel
Als nächstes betrachten wir folgenden Digraphen:
1
2
5 4
32
−2
10
−3
1
43
d2 1 2 3 4 5
1 ∞ 2 ∞ ∞ −1
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ −5
4 ∞ ∞ 4 ∞ ∞
5 10 12 3 1 9
d3 1 2 3 4 5
1 ∞ 2 ∞ ∞ −1
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ −5
4 ∞ 2 4 ∞ −1
5 10 1 3 1 −2
Der Floyd-Warshall-Algorithmus
Beispiel
Als nächstes betrachten wir folgenden Digraphen:
1
2
5 4
32
−2
10
−3
1
43
d3 1 2 3 4 5
1 ∞ 2 ∞ ∞ −1
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ −5
4 ∞ 2 4 ∞ −1
5 10 1 3 1 −2
d4 1 2 3 4 5
1
2
3
4
5
Der Floyd-Warshall-Algorithmus
Beispiel
Als nächstes betrachten wir folgenden Digraphen:
1
2
5 4
32
−2
10
−3
1
43
d3 1 2 3 4 5
1 ∞ 2 ∞ ∞ −1
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ −5
4 ∞ 2 4 ∞ −1
5 10 1 3 1 −2
d4 1 2 3 4 5
1
2
3
4
5
Der Floyd-Warshall-Algorithmus
Beispiel
Als nächstes betrachten wir folgenden Digraphen:
1
2
5 4
32
−2
10
−3
1
43
d3 1 2 3 4 5
1 ∞ 2 ∞ ∞ −1
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ −5
4 ∞ 2 4 ∞ −1
5 10 1 3 1 −2
d4 1 2 3 4 5
1
2
3
4
5
Der Floyd-Warshall-Algorithmus
Beispiel
Als nächstes betrachten wir folgenden Digraphen:
1
2
5 4
32
−2
10
−3
1
43
d3 1 2 3 4 5
1 ∞ 2 ∞ ∞ −1
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ −5
4 ∞ 2 4 ∞ −1
5 10 1 3 1 −2
d4 1 2 3 4 5
1 ∞ 2 ∞ ∞ −1
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ −5
4 ∞ 2 4 ∞ −1
5 10 1
Der Floyd-Warshall-Algorithmus
Beispiel
Als nächstes betrachten wir folgenden Digraphen:
1
2
5 4
32
−2
10
−3
1
43
d3 1 2 3 4 5
1 ∞ 2 ∞ ∞ −1
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ −5
4 ∞ 2 4 ∞ −1
5 10 1 3 1 −2
d4 1 2 3 4 5
1 ∞ 2 ∞ ∞ −1
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ −5
4 ∞ 2 4 ∞ −1
5 10 1 3 1 −2
Der Floyd-Warshall-Algorithmus
Beispiel
Als nächstes betrachten wir folgenden Digraphen:
1
2
5 4
32
−2
10
−3
1
43
d4 1 2 3 4 5
1 ∞ 2 ∞ ∞ −1
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ −5
4 ∞ 2 4 ∞ −1
5 10 1 3 1 −2
d5 1 2 3 4 5
1
2
3
4
5
Der Floyd-Warshall-Algorithmus
Beispiel
Als nächstes betrachten wir folgenden Digraphen:
1
2
5 4
32
−2
10
−3
1
43
d4 1 2 3 4 5
1 ∞ 2 ∞ ∞ −1
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ −5
4 ∞ 2 4 ∞ −1
5 10 1 3 1 −2
d5 1 2 3 4 5
1
2
3
4
5
Der Floyd-Warshall-Algorithmus
Beispiel
Als nächstes betrachten wir folgenden Digraphen:
1
2
5 4
32
−2
10
−3
1
43
d4 1 2 3 4 5
1 ∞ 2 ∞ ∞ −1
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ −5
4 ∞ 2 4 ∞ −1
5 10 1 3 1 −2
d5 1 2 3 4 5
1
2
3
4
5
Der Floyd-Warshall-Algorithmus
Beispiel
Als nächstes betrachten wir folgenden Digraphen:
1
2
5 4
32
−2
10
−3
1
43
d4 1 2 3 4 5
1 ∞ 2 ∞ ∞ −1
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ −5
4 ∞ 2 4 ∞ −1
5 10 1 3 1 −2
d5 1 2 3 4 5
1
2
3
4
5
Der Floyd-Warshall-Algorithmus
Beispiel
Als nächstes betrachten wir folgenden Digraphen:
1
2
5 4
32
−2
10
−3
1
43
d4 1 2 3 4 5
1 ∞ 2 ∞ ∞ −1
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ −5
4 ∞ 2 4 ∞ −1
5 10 1 3 1 −2
d5 1 2 3 4 5
1 9 0 2 0 −3
2 7 −2 0 −2 −5
3 5 −4 −2 −4 −7
4 9 0 2 0 −3
5 8 −1 1 −1 −4
![[ 8 ] VintageDreams Pink Floyd - · PDF fileFotos: Getty Images [ 9 ] Scherzhaft nannte man sie „die führende Band im All“. Aber auch auf der Erde hatten Pink Floyd einiges zu](https://img.pdfslide.org/doc/110x75/5a79ad067f8b9ae1468d5df9/-8-vintagedreams-pink-floyd-getty-images-9-scherzhaft-nannte-man-sie-die.jpg)
