Embed Size (px)
Citation preview
Der Floyd-Warshall-Algorithmus
Beispiel
Betrachte folgenden kantenbewerteten Digraphen:
1
2
5 4
32
−2
10
−3
1
49
d0 1 2 3 4 5
1
2
3
4
5
Der Floyd-Warshall-Algorithmus
Beispiel
Betrachte folgenden kantenbewerteten Digraphen:
1
2
5 4
32
−2
10
−3
1
49
d0 1 2 3 4 5
1 ∞ 2 ∞ ∞ ∞
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ ∞
4 ∞ ∞ 4 ∞ ∞
5 10 ∞ 9 1 ∞
Der Floyd-Warshall-Algorithmus
Beispiel
Betrachte folgenden kantenbewerteten Digraphen:
1
2
5 4
32
−2
10
−3
1
49
d0 1 2 3 4 5
1 ∞ 2 ∞ ∞ ∞
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ ∞
4 ∞ ∞ 4 ∞ ∞
5 10 ∞ 9 1 ∞
d1 1 2 3 4 5
1
2
3
4
5
Der Floyd-Warshall-Algorithmus
Beispiel
Betrachte folgenden kantenbewerteten Digraphen:
1
2
5 4
32
−2
10
−3
1
49
d0 1 2 3 4 5
1 ∞ 2 ∞ ∞ ∞
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ ∞
4 ∞ ∞ 4 ∞ ∞
5 10 ∞ 9 1 ∞
d1 1 2 3 4 5
1
2
3
4
5
Der Floyd-Warshall-Algorithmus
Beispiel
Betrachte folgenden kantenbewerteten Digraphen:
1
2
5 4
32
−2
10
−3
1
49
d0 1 2 3 4 5
1 ∞ 2 ∞ ∞ ∞
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ ∞
4 ∞ ∞ 4 ∞ ∞
5 10 ∞ 9 1 ∞
d1 1 2 3 4 5
1 ∞ 2 ∞ ∞ ∞
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ ∞
4 ∞ ∞ 4 ∞ ∞
5 10 12 9 1 ∞
Der Floyd-Warshall-Algorithmus
Beispiel
Betrachte folgenden kantenbewerteten Digraphen:
1
2
5 4
32
−2
10
−3
1
49
d1 1 2 3 4 5
1 ∞ 2 ∞ ∞ ∞
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ ∞
4 ∞ ∞ 4 ∞ ∞
5 10 12 9 1 ∞
d2 1 2 3 4 5
1
2
3
4
5
Der Floyd-Warshall-Algorithmus
Beispiel
Betrachte folgenden kantenbewerteten Digraphen:
1
2
5 4
32
−2
10
−3
1
49
d1 1 2 3 4 5
1 ∞ 2 ∞ ∞ ∞
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ ∞
4 ∞ ∞ 4 ∞ ∞
5 10 12 9 1 ∞
d2 1 2 3 4 5
1
2
3
4
5
Der Floyd-Warshall-Algorithmus
Beispiel
Betrachte folgenden kantenbewerteten Digraphen:
1
2
5 4
32
−2
10
−3
1
49
d1 1 2 3 4 5
1 ∞ 2 ∞ ∞ ∞
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ ∞
4 ∞ ∞ 4 ∞ ∞
5 10 12 9 1 ∞
d2 1 2 3 4 5
1
2
3
4
5
Der Floyd-Warshall-Algorithmus
Beispiel
Betrachte folgenden kantenbewerteten Digraphen:
1
2
5 4
32
−2
10
−3
1
49
d1 1 2 3 4 5
1 ∞ 2 ∞ ∞ ∞
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ ∞
4 ∞ ∞ 4 ∞ ∞
5 10 12 9 1 ∞
d2 1 2 3 4 5
1 ∞ 2 ∞ ∞
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞
4 ∞ ∞ 4 ∞ ∞
5 10 12 9 1
Der Floyd-Warshall-Algorithmus
Beispiel
Betrachte folgenden kantenbewerteten Digraphen:
1
2
5 4
32
−2
10
−3
1
49
d1 1 2 3 4 5
1 ∞ 2 ∞ ∞ ∞
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ ∞
4 ∞ ∞ 4 ∞ ∞
5 10 12 9 1 ∞
d2 1 2 3 4 5
1 ∞ 2 ∞ ∞ −1
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ −5
4 ∞ ∞ 4 ∞ ∞
5 10 12 9 1 9
Der Floyd-Warshall-Algorithmus
Beispiel
Betrachte folgenden kantenbewerteten Digraphen:
1
2
5 4
32
−2
10
−3
1
49
d2 1 2 3 4 5
1 ∞ 2 ∞ ∞ −1
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ −5
4 ∞ ∞ 4 ∞ ∞
5 10 12 9 1 9
d3 1 2 3 4 5
1
2
3
4
5
Der Floyd-Warshall-Algorithmus
Beispiel
Betrachte folgenden kantenbewerteten Digraphen:
1
2
5 4
32
−2
10
−3
1
49
d2 1 2 3 4 5
1 ∞ 2 ∞ ∞ −1
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ −5
4 ∞ ∞ 4 ∞ ∞
5 10 12 9 1 9
d3 1 2 3 4 5
1
2
3
4
5
Der Floyd-Warshall-Algorithmus
Beispiel
Betrachte folgenden kantenbewerteten Digraphen:
1
2
5 4
32
−2
10
−3
1
49
d2 1 2 3 4 5
1 ∞ 2 ∞ ∞ −1
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ −5
4 ∞ ∞ 4 ∞ ∞
5 10 12 9 1 9
d3 1 2 3 4 5
1
2
3
4
5
Der Floyd-Warshall-Algorithmus
Beispiel
Betrachte folgenden kantenbewerteten Digraphen:
1
2
5 4
32
−2
10
−3
1
49
d2 1 2 3 4 5
1 ∞ 2 ∞ ∞ −1
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ −5
4 ∞ ∞ 4 ∞ ∞
5 10 12 9 1 9
d3 1 2 3 4 5
1 ∞ 2 ∞ ∞ −1
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ −5
4 ∞ 4 ∞
5 10 9 1
Der Floyd-Warshall-Algorithmus
Beispiel
Betrachte folgenden kantenbewerteten Digraphen:
1
2
5 4
32
−2
10
−3
1
49
d2 1 2 3 4 5
1 ∞ 2 ∞ ∞ −1
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ −5
4 ∞ ∞ 4 ∞ ∞
5 10 12 9 1 9
d3 1 2 3 4 5
1 ∞ 2 ∞ ∞ −1
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ −5
4 ∞ 2 4 ∞ −1
5 10 7 9 1 4
Der Floyd-Warshall-Algorithmus
Beispiel
Betrachte folgenden kantenbewerteten Digraphen:
1
2
5 4
32
−2
10
−3
1
49
d3 1 2 3 4 5
1 ∞ 2 ∞ ∞ −1
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ −5
4 ∞ 2 4 ∞ −1
5 10 7 9 1 4
d4 1 2 3 4 5
1
2
3
4
5
Der Floyd-Warshall-Algorithmus
Beispiel
Betrachte folgenden kantenbewerteten Digraphen:
1
2
5 4
32
−2
10
−3
1
49
d3 1 2 3 4 5
1 ∞ 2 ∞ ∞ −1
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ −5
4 ∞ 2 4 ∞ −1
5 10 7 9 1 4
d4 1 2 3 4 5
1
2
3
4
5
Der Floyd-Warshall-Algorithmus
Beispiel
Betrachte folgenden kantenbewerteten Digraphen:
1
2
5 4
32
−2
10
−3
1
49
d3 1 2 3 4 5
1 ∞ 2 ∞ ∞ −1
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ −5
4 ∞ 2 4 ∞ −1
5 10 7 9 1 4
d4 1 2 3 4 5
1
2
3
4
5
Der Floyd-Warshall-Algorithmus
Beispiel
Betrachte folgenden kantenbewerteten Digraphen:
1
2
5 4
32
−2
10
−3
1
49
d3 1 2 3 4 5
1 ∞ 2 ∞ ∞ −1
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ −5
4 ∞ 2 4 ∞ −1
5 10 7 9 1 4
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
Betrachte folgenden kantenbewerteten Digraphen:
1
2
5 4
32
−2
10
−3
1
49
d3 1 2 3 4 5
1 ∞ 2 ∞ ∞ −1
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ −5
4 ∞ 2 4 ∞ −1
5 10 7 9 1 4
d4 1 2 3 4 5
1 ∞ 2 ∞ ∞ −1
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ −5
4 ∞ 2 4 ∞ −1
5 10 3 5 1 0
Der Floyd-Warshall-Algorithmus
Beispiel
Betrachte folgenden kantenbewerteten Digraphen:
1
2
5 4
32
−2
10
−3
1
49
d4 1 2 3 4 5
1 ∞ 2 ∞ ∞ −1
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ −5
4 ∞ 2 4 ∞ −1
5 10 3 5 1 0
d5 1 2 3 4 5
1
2
3
4
5
Der Floyd-Warshall-Algorithmus
Beispiel
Betrachte folgenden kantenbewerteten Digraphen:
1
2
5 4
32
−2
10
−3
1
49
d4 1 2 3 4 5
1 ∞ 2 ∞ ∞ −1
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ −5
4 ∞ 2 4 ∞ −1
5 10 3 5 1 0
d5 1 2 3 4 5
1
2
3
4
5
Der Floyd-Warshall-Algorithmus
Beispiel
Betrachte folgenden kantenbewerteten Digraphen:
1
2
5 4
32
−2
10
−3
1
49
d4 1 2 3 4 5
1 ∞ 2 ∞ ∞ −1
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ −5
4 ∞ 2 4 ∞ −1
5 10 3 5 1 0
d5 1 2 3 4 5
1
2
3
4
5
Der Floyd-Warshall-Algorithmus
Beispiel
Betrachte folgenden kantenbewerteten Digraphen:
1
2
5 4
32
−2
10
−3
1
49
d4 1 2 3 4 5
1 ∞ 2 ∞ ∞ −1
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ −5
4 ∞ 2 4 ∞ −1
5 10 3 5 1 0
d5 1 2 3 4 5
1 −1
2 −3
3 −5
4 −1
5 10 3 5 1 0
Der Floyd-Warshall-Algorithmus
Beispiel
Betrachte folgenden kantenbewerteten Digraphen:
1
2
5 4
32
−2
10
−3
1
49
d4 1 2 3 4 5
1 ∞ 2 ∞ ∞ −1
2 ∞ ∞ ∞ ∞ −3
3 ∞ −2 ∞ ∞ −5
4 ∞ 2 4 ∞ −1
5 10 3 5 1 0
d5 1 2 3 4 5
1 9 2 4 0 −1
2 7 0 2 −2 −3
3 5 −2 0 −4 −5
4 9 2 4 0 −1
5 10 3 5 1 0
![[ 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)
