Question bank — Floyd-Warshall — all-pairs shortest paths, O(V³)

False. Only $k$ must be outermost; $i$ and $j$ may swap freely. The DP recurses on $k$, so every pair must fully account for $\{1,\dots ,k\}$ before $k+1$ is unlocked — an inner $k$ reads half-updated rows.

True. Store $w(i,j)=w(j,i)$ for each undirected edge; the algorithm never assumes asymmetry. But note: an undirected negative edge is a negative cycle (go back and forth), so negative weights become illegal on undirected graphs.

False. min doesn't care about edge sign; negative edges are fine. What it cannot handle is a negative cycle — see Bellman-Ford and Negative Cycles for the distinction.

True. A negative cycle through $i$ forces $d(i,i)<0$; if no diagonal entry dropped below $0$, no such cheaper-than-staying loop exists.

False. For dense graphs ($E\approx V^2$) both are near $O(V^3)$, and Dijkstra breaks on negative edges entirely. Dijkstra-from-all wins only on sparse, non-negative graphs (see Dijkstra's Algorithm).

False. In iteration $k$ the entries $d[i][k]$ and $d[k][j]$ do not change (they'd only change via $d[k][k]=0$), so reading them mid-sweep is safe.

True (given no negative cycle). A simple shortest path visits each vertex once, so it has $\le V-1$ edges; unlocking all $V$ intermediates captures every such path.

Error: loop order. Innermost $k$ means for a fixed $(i,j)$ you sweep all $k$ before finishing other pairs, so $d[i][k]$ and $d[k][j]$ are still stuck at layer $k-1$ for pairs you haven't reached — you read stale data and mix layers. $k$ must be outermost.

Error: edge vs cycle. A single negative edge is harmless. You must check the sum around a loop: after the run, look for $d(i,i)<0$. Negative edges are legal; negative cycles are not.

Error: diagonal base case. The diagonal must start at $0$ ("staying put costs nothing"). If it's $\infty$, the split-at-$k$ logic breaks and the negative-cycle test loses its baseline.

Error: wrong successor. Store next[i][j] = next[i][k], the first hop toward $k$, not $k$ itself. next holds the immediate next vertex; jumping straight to $k$ skips the segment $i\to k$.

Error: contamination. Once any $d(i,i)<0$, distances for pairs whose shortest path can reach the cycle are meaningless ($-\infty$). You must detect and abort (or use Johnson's Algorithm semantics), not trust the matrix.

Error: overflow via $\infty +\infty$. Adding two "infinity" sentinels overflows or produces a finite-looking sum that beats a real distance. Guard relaxations with if d[i][k] < INF and d[k][j] < INF, or use a genuinely unreachable value.

With no negative cycle, an optimal path visits $k$ exactly once; revisiting would form a cycle that only adds cost. So neither half needs $k$ as an intermediate — each is a $\{1,\dots ,k-1\}$ subproblem, and the DP closes on itself.

$d(i,i)$ starts at $0$ (cost of not moving). The only way to make a round-trip $i\to \cdots \to i$ cheaper than $0$ is a loop whose weights sum below $0$ — i.e. a negative cycle through $i$. The diagonal is a free cycle-detector.

Bellman-Ford-from-all is $O(V^{2}E)$; with $E\approx V^2$ that's $O(V^4)$. Floyd-Warshall is a flat $O(V^3)$ regardless of density, and it's five lines.

The in-place trick reuses one matrix, so each of $V$ values of $k$ does a single $V\times V$ sweep: $V\cdot V\cdot V=V^3$. We never store $V$ separate layers.

Without a restriction there's no smaller subproblem to recurse on — the answer would depend on itself circularly. The $k$-restriction gives a strict ordering ($k-1$ before $k$) that makes the recurrence well-founded, the essence of Dynamic Programming.

Floyd-Warshall revisits every pair for every $k$, so a later negative detour can still overwrite an earlier commitment. Dijkstra finalizes a vertex once and never reopens it, which a negative edge can invalidate.

Replace $\min$/$+$ with OR/AND on booleans: reach[i][j] |= reach[i][k] and reach[k][j]. The "unlock $k$" skeleton is identical — see Transitive Closure.

The diagonal is $0$ and every off-diagonal entry stays $\infty$ — correctly saying "no vertex reaches any other, but each reaches itself at cost $0$."

The diagonal stays $0$ because staying put (cost $0$) always beats taking a positive loop. The self-loop is silently ignored, which is correct.

That is a negative cycle of length one; $d(i,i)$ drops below $0$ and the negative-cycle test fires. Distances become unreliable, as expected.

$d(i,j)$ is finite (a real path exists) while $d(j,i)$ stays $\infty$. The matrix is asymmetric — Floyd-Warshall respects edge direction.

Yes. The $1\times 1$ matrix is $[0]$, the $k=0$ sweep changes nothing, output $d(0,0)=0$. A valid degenerate case.

No. Both diagonals stay $0$; a positive round-trip never beats staying put. Negative cycles require the loop sum to be below $0$, not merely the existence of a return edge.

No. A zero-sum loop leaves $d(i,i)=0$ (equal, not less). "Shortest" is still well-defined; the algorithm treats it as harmless.

Whichever relaxation fired first wins, since ties (<, strict) don't overwrite. The distance is unique; the path reported is implementation-order-dependent but valid.