Algorithmus von Floyd und Warshall
Algorithmus der Graphentheorie / aus Wikipedia, der freien encyclopedia
Liebe Wikiwand-AI, fassen wir uns kurz, indem wir einfach diese Schlüsselfragen beantworten:
Können Sie die wichtigsten Fakten und Statistiken dazu auflisten Algorithmus von Floyd und Warshall?
Fass diesen Artikel für einen 10-Jährigen zusammen
ZEIGE ALLE FRAGEN
Der Algorithmus von Floyd und Warshall (auch Floyd-Warshall-Algorithmus oder Tripel-Algorithmus), benannt nach Robert Floyd und Stephen Warshall, ist ein Algorithmus der Graphentheorie. In Floyds Version findet er die kürzesten Pfade zwischen allen Paaren von Knoten eines Graphen und berechnet deren Länge (APSP, all-pairs shortest path). In Warshalls Version findet er die transitive Hülle eines Graphen. Beide Versionen wurden 1962 vorgestellt und gehen auf einen Algorithmus zurück, den Stephen Kleene 1956 im Zusammenhang mit regulären Ausdrücken veröffentlicht hat.