Micro-questions over the Floyd–Warshall module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.
A. The all-pairs question
1. Name four questions that are not about one source.
Answer
- The diameter of a network — the largest shortest-path distance between any two nodes.
- A precomputed routing table answering queries in .
- Transitive closure — which pairs are connected at all.
- Arbitrage detection — is there a negative cycle.
2. What is the obvious approach, and when is it right?
Answer
Run a single-source algorithm times. For sparse graphs it is the right answer.
3. What is Floyd–Warshall’s completely different route?
Answer
It never thinks about paths at all. It thinks about which vertices a path is allowed to pass through.
B. The vocabulary
4. What is the all-pairs shortest path problem?
Answer
Computing the shortest distance between every ordered pair of vertices — a table rather than a single array.
5. What is an intermediate vertex?
Answer
A vertex a path passes through — neither its start nor its end. In the intermediates are and . This is the concept the entire algorithm is organised around.
6. What is the distance matrix, and what does it start and end as?
Answer
— the best known cost from to . It starts as the adjacency matrix (direct edges only) and ends as the true shortest distances.
7. What is the next matrix?
Answer
Also the successor matrix — next[i][j] is the first vertex to move to when travelling from towards along the best route. It is how you recover an actual path from a table of costs.
8. What is round , precisely?
Answer
One pass of the outer loop, during which vertex becomes newly permitted as an intermediate. After round , holds the shortest path using only the first vertices as intermediates.
9. What is transitive closure, and what is that variant called?
Answer
The table of which vertices are reachable from which, ignoring cost. It is Floyd–Warshall with replaced by or and by and — called Warshall’s algorithm.
C. The idea
10. State the reframing that makes the algorithm obvious.
Answer
Do not ask “what is the shortest path from to ?” Ask “what is the shortest path from to that is only allowed to pass through vertices from some permitted set?”
11. What is the base case, and why is it free?
Answer
The permitted set is empty, so the only routes are direct edges — the answer is just the adjacency matrix.
12. When you permit one more vertex , what are the only two possibilities?
Answer
The best route either does not use (unchanged from before), or does use — going , where both halves are already solved because they use only previously permitted intermediates.
13. Write the recurrence.
Answer
14. Say the recurrence in words.
Answer
The shortest path allowed to use the first vertices is either the one that ignores entirely, or the best route into followed by the best route out of it.
15. Write the whole algorithm.
Answer
for k in vertices:
for i in vertices:
for j in vertices:
if d[i][k] + d[k][j] < d[i][j]:
d[i][j] = d[i][k] + d[k][j]
nxt[i][j] = nxt[i][k]16. Why is considering each exactly once enough?
Answer
Revisiting a vertex means the path contains a cycle, and (absent negative cycles) removing that cycle never lengthens it. So a simple shortest path always exists, and a simple path uses each vertex at most once as an intermediate.
17. What is striking about how it finds a three-edge path like ?
Answer
It finds it without ever enumerating a path. It composes it from two halves, each itself composed from halves.
18. How do you recover the actual route?
Answer
One extra line on improvement: nxt[i][j] = nxt[i][k] — the first step from is whatever the first step towards was. Then walk by repeatedly setting i = nxt[i][j] until i == j.
D. The loop order
19. Does the algorithm still work if you swap outermost and innermost?
Answer
No — and this is the single most important thing in the lesson.
20. What exactly does the outer loop guarantee?
Answer
That when you consider routing through , the values and are already final with respect to all previously permitted intermediates — because round begins only after round has finished for every pair.
21. What goes wrong with on the inside?
Answer
You use before has itself been improved. The result is an overestimate — a real path, but not the shortest one.
22. How often is the wrong order actually wrong?
Answer
On 105 of 200 random graphs in the lab. Not a corner case — wrong most of the time. It survives in people’s memory because on small or nearly-complete graphs it often coincidentally agrees.
E. Negative cycles
23. What does start at, and what does it mean if it goes negative?
Answer
It starts at 0 — the cost of going nowhere. It can only go negative if there is a route that leaves , comes back, and costs less than nothing.
24. State the detection rule.
Answer
A negative cycle exists iff some after the algorithm finishes. One scan of the diagonal, , no extra pass.
25. What is true of the off-diagonal numbers when a negative cycle exists?
Answer
They are meaningless — detect and report, do not use. As with Bellman–Ford.
26. What caution do textbooks gloss over here?
Answer
With a negative cycle present, the loop can propagate arbitrarily negative values, and with floating-point weights this can reach or produce nan. Detect the cycle and stop, rather than handing the matrix downstream.
F. Choosing
27. Compare Floyd–Warshall with Dijkstras across six rows.
Answer
| Floyd–Warshall | Dijkstra | |
|---|---|---|
| Cost | always | |
| Negative weights | yes | no |
| Negative cycle detection | yes, diagonal | no |
| Space | output | |
| Lines of code | ~5 | ~20 |
| Best when | dense, small | sparse |
28. State the rule of thumb.
Answer
If is close to , use Floyd–Warshall. If is closer to , run Dijkstra times.
29. At , , what is the gap?
Answer
Floyd–Warshall does operations; Dijkstras do about — about 14× slower, and worsening as the graph grows.
30. Negative weights, sparse graph, all pairs needed — what is the right answer?
Answer
Johnson’s algorithm: one Bellman–Ford run to reweight every edge non-negative, then Dijkstras on the reweighted graph. with negative weights allowed.
31. What is Floyd–Warshall’s real practical niche?
Answer
Small dense graphs, where its five lines beat twenty lines of Dijkstra on engineering time. caps you at a few thousand vertices — at that is operations.
G. The operator family
32. Why do other operator pairs work in the same triple loop?
Answer
Any pair of operators forming a semiring, where one distributes over the other, works identically.
33. Give the operator table.
Answer
| Problem | Combine paths | Combine edges | Start |
|---|---|---|---|
| Shortest path | |||
| Transitive closure | or | and | False |
| Widest path / bottleneck | |||
| Most reliable path | 0 | ||
| Counting paths | 0 |
34. Why is recognising the family worth more than the shortest-path version?
Answer
Because “shortest” is only one of the questions it answers — the same five lines solve reachability, bottleneck, reliability and path counting.
H. Traps
35. What must the diagonal be initialised to, and what breaks otherwise?
Answer
0. Start it at infinity and the negative-cycle test never fires, and self-loops get misread.
36. How do you handle parallel edges when building the matrix?
Answer
Keep the minimum. Overwriting blindly means the last one in the list wins, which may not be the cheapest.
37. What is the INF + INF trap?
Answer
Fine with float("inf"). With a large integer sentinel like , adding two gives — which may overflow a fixed-width int in C++ or Java, wrap to negative, and look like a shortest path. Guard with if d[i][k] != INF and d[k][j] != INF.
38. How do you use it on an undirected graph?
Answer
Insert both directions when building the matrix — and remember an undirected negative edge is automatically a negative cycle.
39. Summarise Floyd–Warshall in one sentence.
Answer
Permit one more intermediate vertex per round and take the best of “route ignores it” versus “route goes through it” — five lines, , and only correct with on the outside.
Scorecard
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- Floyd–Warshall — the module
- Bellman–Ford — Question Bank — single source with negative weights
- Dijkstra — Question Bank — the sparse alternative, run times
Software engineering
Infrastructure & security
Computer science
Hardware & engineering