FloydWarshallAlgorithmus

The Floyd-Warshall algorithm is a dynamic programming method for finding shortest paths between all pairs of vertices in a weighted graph. It supports graphs with negative edge weights but requires that no negative-weight cycle be present to yield finite shortest paths for all pairs. The algorithm can be applied to directed or undirected graphs and can also be used to compute transitive closure with a simple modification.

The standard formulation uses a distance matrix dist where dist[i][j] is the weight of the shortest known path from i to j. Initially, dist[i][j] is set to the edge weight from i to j, or to infinity if there is no direct edge; dist[i][i] is set to zero. A corresponding next matrix is often maintained to reconstruct actual paths. The core update proceeds over all possible intermediate vertices k: for every pair (i, j), if dist[i][k] + dist[k][j] < dist[i][j], then dist[i][j] is updated to this smaller value and next[i][j] is set to next[i][k]. This allows paths to be built incrementally as more intermediate vertices are considered.

The algorithm runs in O(n^3) time and uses O(n^2) space, where n is the number of vertices. It is robust to negative edge weights but will detect negative cycles by checking if dist[i][i] becomes negative for any i after the updates; such cycles imply that no finite shortest paths exist for some pairs that are reachable from the cycle.

Historically, the method is attributed to Robert Floyd, building on earlier work by Stephen Warshall. It remains a fundamental baseline technique for all-pairs shortest paths and is widely taught in algorithm courses and used in network design, routing, and related applications.