Floyd-Warshall has finished on a directed graph with some negative edge weights.
Which feature of the final matrix says the graph has a negative cycle?

Question

Floyd-Warshall has finished on a directed graph with some negative edge weights. Which feature of the final matrix says the graph has a negative cycle?

Accepted Answer

Some diagonal entry  dist[v][v]  is negative

Answer

The matrix is not symmetric

Answer

Some entry anywhere in the matrix is negative

Answer

Some entry is still ∞

Crowdly

Floyd-Warshall has finished on a directed graph with some negative edge weights....

Want instant access to all verified answers on learning.monash.edu?