Opening your learning space
Starting the app …
Opening your learning space
Starting the app …
Floyd–Warshall computes all-pairs shortest paths by successively allowing each vertex as an intermediate node.
Free to browse · flashcards or a multiple-choice quiz · import from Essential
Formula
Distances use the additive edge-weight unit; runtime O(V3), memory O(V2)
| Symbol | Meaning | Unit |
|---|---|---|
| Current distance from i to j | sum of edge weights | |
| Newly allowed intermediate vertex | vertex index | |
| Number of vertices | count |
D_{ij}^{(k)}=\min(D_{ij}^{(k-1)},D_{ik}^{(k-1)}+D_{kj}^{(k-1)})Initialize Dii=0, direct edges with their weights and missing edges with infinity. Update with loops ordered k,i,j. Negative edges are allowed if no negative cycle exists; a negative diagonal after completion signals one. Paths affected by a negative cycle are unbounded below. The algorithm uses Θ(V3) time and Θ(V2) space.
Initialize Dii=0, direct edges with their weights and missing edges with infinity. Update with loops ordered k,i,j. Negative edges are allowed if no negative cycle exists; a negative diagonal after completion signals one. Paths affected by a negative cycle are unbounded below. The algorithm uses Θ(V3) time and Θ(V2) space.
Floyd–Warshall computes all-pairs shortest paths by successively allowing each vertex as an intermediate node.
Weg über k übernehmen
Initialize the diagonal to zero and preserve the k,i,j update order.
Use the example for Floyd–Warshall algorithm to explain which inputs determine the requested output.
The example connects concrete inputs to its result.
Floyd–Warshall computes all-pairs shortest paths by successively allowing each vertex as an intermediate node.
The relation applies only under its stated assumptions.
Applying the relation to a different case without checking its stated assumptions.
Check the validity range before substituting values: Initialize Dii=0, direct edges with their weights and missing edges with infinity. Update with loops ordered k,i,j. Negative edges are allowed if no negative cycle exists; a negative diagonal after.
Formula cluster
Floyd–Warshall computes all-pairs shortest paths by successively allowing each vertex as an intermediate node.
For directed edges A→B=3, B→C=−1 and A→C=5, allowing B gives DAC=min(5,3−1)=2. The route A→B→C improves on the direct edge; this graph has no negative cycle.
Solve all-pairs shortest paths in small or dense directed graphs.
Here is how to work through a typical Floyd–Warshall algorithm (Dᵢⱼ ← min(Dᵢⱼ, Dᵢₖ + Dₖⱼ)) task step by step:
Task
Use the example for Floyd–Warshall algorithm to explain which inputs determine the requested output.
Solution path
The example connects concrete inputs to its result.
Floyd–Warshall computes all-pairs shortest paths by successively allowing each vertex as an intermediate node.
The relation applies only under its stated assumptions.
After processing k, Dij is the best route from i to j whose internal vertices are among processed vertices. The update compares the current route with one via k. Dynamic programming works because a route either avoids k or uses it; a shortest route through k splits into two subroutes. Distances add along directed paths. Negative edges are allowed, but a negative cycle makes some shortest-walk values unbounded below. Missing direct edges are usually initialized to infinity, with zero on the diagonal. An undirected edge is represented by two opposite directed entries in the initial matrix.
The invariant depends on which intermediate vertices have already been allowed. An outer k loop completes each dynamic-programming stage before the next. If i or j is outermost in the usual in-place implementation, values may be reused in an order inconsistent with the invariant. Results can be wrong even when the recurrence looks unchanged. Distances add along directed paths. Negative edges are allowed, but a negative cycle makes some shortest-walk values unbounded below. Document this invariant alongside the loop order in an implementation. The invariant records which intermediate vertices are allowed after each completed k-stage.
Yes. Unlike Dijkstra, Floyd–Warshall handles negative edge weights, provided no negative cycle makes a shortest walk unbounded below. After updates, a negative diagonal entry Dii indicates a cycle reachable from and returning to i with negative total weight. Flag affected pairs instead of reporting finite shortest distances. Distances add along directed paths. Negative edges are allowed, but a negative cycle makes some shortest-walk values unbounded below. A negative cycle is a limitation of the shortest-path model, rather than a numerical exception. A negative diagonal identifies a cycle; affected reachable pairs must then be marked.
The algorithm considers each of V vertices as an intermediate. For every k it examines all ordered pairs (i,j), giving V3 updates. It stores a V-by-V distance matrix, hence Θ(V2) memory. This is useful for moderate dense graphs; repeated single-source methods may suit large sparse graphs better. Distances add along directed paths. Negative edges are allowed, but a negative cycle makes some shortest-walk values unbounded below. The matrix representation also explains the quadratic storage requirement. For very large sparse graphs, matrix storage can motivate a different representation or algorithm.
Initially the direct distance from A to C is 5. When B is allowed, the route through B costs DAB+DBC=3+(−1)=2, so the update stores 2. This matches path A→B→C and is finite because the graph has no return route forming a negative cycle. Distances add along directed paths. Negative edges are allowed, but a negative cycle makes some shortest-walk values unbounded below. The example graph has no return edge that could form a cycle with its two edges. A negative edge alone is harmless; a return path is needed to form a cycle.
Quanta exam set
Curated exam set for "Floyd–Warshall algorithm":
Question (front)
Which formula describes Floyd–Warshall algorithm?
Answer in your set
Question (front)
How do you rearrange Floyd–Warshall algorithm for Weg über k übernehmen?
Answer in your set
Question (front)
Which common mistake happens with Floyd–Warshall algorithm?
Answer in your set
+ 7 more cards: units, variables, derivation, example, exam task
The formula set contains 10 cards. After importing, review them and start practicing; your ratings determine later review intervals.
This list names subject references and further reading. A page or section number appears when it is part of the reference; these are not verbatim quotations.
Create a curated FSRS exam set for Dᵢⱼ ← min(Dᵢⱼ, Dᵢₖ + Dₖⱼ): formula recall, variables, derivation, rearrangement, worked example, common mistakes and exam context.
Curated formula set · LaTeX · FSRS spaced repetition · import from Essential