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
  1. The diameter of a network — the largest shortest-path distance between any two nodes.
  2. A precomputed routing table answering queries in .
  3. Transitive closure — which pairs are connected at all.
  4. 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 weightsyesno
Negative cycle detectionyes, diagonalno
Space output
Lines of code~5~20
Best whendense, 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
ProblemCombine pathsCombine edgesStart
Shortest path
Transitive closureorandFalse
Widest path / bottleneck
Most reliable path0
Counting paths0

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

PassDateGot itCloseBlankQuestions missed
1
2
3

↑ Back to Graph Algorithms