All Pairs Shortest Paths
Channel: Videothek Algorithmik
Date: 27/06/2015

1. [00:00] Einführung
2. [00:07] Einführendes Beispiel
3. [04:43] Wie sieht das für ein einzelnes Knotenpaar aus?
4. [05:31] Können wir noch ein Knotenpaar sehen?
5. [06:10] Was ist mit negativen Zyklen?
6. [08:27] Beschleunigung: Repeated Squaring
7. [11:54] Floyd-Warshal
8. [16:07] Wie lautet die Invariante? (Bellman-Ford)
9. [16:22] Warum ist der Algorithmus korrekt? (Bellman-Ford)
10. [17:15] Wie wird die Invariante sichergestellt? (Bellman-Ford)
11. [18:11] Was ist die asymptotische Komplexität des Algorithmus? (Bellman-Ford)
12. [18:50] Was war das noch? (Repeated Squaring)
13. [19:50] Wie lautet die Invariante? (Floyd-Warshal)
14. [20:10] Wie wird die Invariante sichergestellt? (Floyd-Warshal)
15. [21:07] Was ist die asymptotische Komplexität des Algorithmus? (Floyd-Warshal)