Der Floyd-Warshall-Algorithmus ist ein graphentheoretisches Verfahren zur Bestimmung der kürzesten Wege zwischen allen Paaren von Knoten in einem gewichteten Graphen. Er funktioniert sowohl für gerichtete als auch für ungerichtete Graphen und kann positive sowie negative Gewichtungen verarbeiten, solange es keine negativen Zyklen gibt. Der Algorithmus basiert auf der dynamischen Programmierung und nutzt eine Matrix, um die aktuellen Abstände zwischen den Knoten zu speichern.
Die Grundidee ist, dass der kürzeste Weg zwischen zwei Knoten und möglicherweise über einen dritten Knoten verläuft. Die Aktualisierungsformel lautet:
Hierbei steht für die aktuelle Distanz zwischen den Knoten und . Der Algorithmus wird in Zeit ausgeführt, wobei die Anzahl der Knoten ist. Am Ende werden alle kürzesten Wege in der Matrix gespeichert, was den Algorithmus besonders nützlich für Anwendungen macht, die eine vollständige Distanzmatrix benötigen.
Starte dein personalisiertes Lernelebnis mit acemate. Melde dich kostenlos an und finde Zusammenfassungen und Altklausuren für deine Universität.