Der Floyd-Warshall-Algorithmus ist ein effizientes Verfahren zur Bestimmung der kürzesten Pfade zwischen allen Paaren von Knoten in einem gewichteten Graphen. Er basiert auf der Idee, dass der kürzeste Pfad zwischen zwei Knoten entweder direkt oder über einen dritten Knoten führt. Der Algorithmus nutzt eine dynamische Programmierungstechnik und aktualisiert eine Distanzmatrix, die alle kürzesten Distanzen zwischen Knoten speichert.
Die Grundidee ist, die Matrix iterativ zu aktualisieren, indem man überprüft, ob der Pfad von Knoten zu Knoten über Knoten kürzer ist als der bisher bekannte Pfad. Dies wird durch die folgende Beziehung beschrieben:
Hierbei ist die aktuelle kürzeste Distanz zwischen den Knoten und . Der Algorithmus hat eine Zeitkomplexität von , wobei die Anzahl der Knoten im Graphen ist, und eignet sich besonders gut für dichte Graphen oder wenn man alle kürzesten Wege auf einmal berechnen möchte.
Starte dein personalisiertes Lernelebnis mit acemate. Melde dich kostenlos an und finde Zusammenfassungen und Altklausuren für deine Universität.