Next:
Grundlegende Begriffe
Up:
Inhalt
Previous:
Prim's Algorithmus, zweite Variante
Kürzeste Pfade
Grundlegende Begriffe
Das single-source-shortest-path-Problem
Dijkstra's Algorithmus
Dikstra's Algorithmus mit Radix-Heaps
Bellman-Ford-Algorithmus
Floyd's Algorithmus für das All-pairs-shortest-path-Problem
Digraphen mit negativen Kantengewichten
Grundsätzliches
Modifikation von Bellman-Ford-Algorithmus
Modifikation von Floyd's-Algorithmus
Der Algorithmus von Johnson
Zusammenfassung
Transitive Hülle
Min-Plus-Matrix-Produkt und Min-Plus-Transitive Hülle
Boolesche Matrixmuliplikation und Transitive Hülle
Der 4-Russen-Algorithmus für Boolesche Matrixmultiplikation
Transitive Hülle und DFS
Ein besserer Algorithmus für das All-pairs-shortest-distance (bzw. paths)-Problem in ungewichteten Digraphen
Ein Algorithmus für die transitive Hülle in Digraphen mit linearer erwarteter Laufzeit
Matrizenmultiplikation à la Strassen
Abbas-Bardia Kabiri-Jarghouyeh
3/3/1999