Floyd-Warshall Algorithm and negative-weights? a. What do the main diagonal entries of the D matrix constructed by

Floyd-Warshall Algorithm and negative-weights?

 

Transcribed Image Text:

a. What do the main diagonal entries of the D matrix constructed by the Floyd-Warshall algorithm represent? b. How can we use the diagonal entries to detect negative weight cycles? D(5)= 0 3 7 2 -1 8 5 1 0 4 -3 2 -4 -4 1 -1 05 3 -5 0-2 1 6 0 (5) FLOYD-WARSHALL' (W) 1 n = W.rows 2 D = W 3 for k=1 to n 4 5 6 7 return D NIL 4 4 4 4 for i=1 to n 3 4 4 NIL 3 3 3 NIL 4 4 for j = 1 to n 5 2 2 dij = min (dij, dik + dkj) NIL 1 I 1 5 NIL a. What do the main diagonal entries of the D matrix constructed by the Floyd-Warshall algorithm represent? b. How can we use the diagonal entries to detect negative weight cycles? D(5)= 0 3 7 2 -1 8 5 1 0 4 -3 2 -4 -4 1 -1 05 3 -5 0-2 1 6 0 (5) FLOYD-WARSHALL' (W) 1 n = W.rows 2 D = W 3 for k=1 to n 4 5 6 7 return D NIL 4 4 4 4 for i=1 to n 3 4 4 NIL 3 3 3 NIL 4 4 for j = 1 to n 5 2 2 dij = min (dij, dik + dkj) NIL 1 I 1 5 NIL