Floyd-Warshall detects the presence of a negative cycle by
Arunning V passes of Bellman-Ford after the main loop
Bchecking if the priority queue is empty
Crebuilding the graph and re-running
Dchecking the diagonal: any d[i][i] < 0 flags a negative cycle
Answer & Solution
Correct answer: D. checking the diagonal: any d[i][i] < 0 flags a negative cycle
After the main loop, the shortest distance from i to itself should be 0 (the empty path). If d[i][i] < 0, the algorithm found a shorter cyclic path through i — a negative cycle. This is the cheapest cycle detection in Floyd-Warshall. Bellman-Ford runs separately and detects via the V-th iteration; the queue idea is Dijkstra-only.
Related questions
An NP-hard problem differs from an NP-complete one because NP-hard problemsThe first problem proved to be NP-complete wasA problem X is NP-complete if and only ifWhy does theoretical computer science draw the line at 'polynomial-time' for tractability?Which set inclusion is established (i.e., proven, not open)?The class NP is the set of decision problems for whichTopological sort is well-defined forThe running time and space of Floyd-Warshall on a graph with V vertices and E edges is