Shortest paths with negative weights Assume we are running Floyd-Warshall on a graph that has no negative cycle. The algorithm keeps a matrix whose entry dist[u][v] is the current estimate of the distance from u to v, and its outer loop runs over the vertices in the order 1, 2, …, |V|. Once the iteration for vertex k has finished, what does dist[u][v] hold?

Question

Accepted Answer

The weight of the shortest u-to-v path whose intermediate vertices all come from 1, …, k, or infinity if there is no such path.

Answer

The weight of the shortest path from u to v that avoids vertex k.

Answer

The weight of the shortest path from u to v that uses at most k edges.

Answer

The final shortest-path weight, for every pair.

Answer

The weight of the shortest path from u to v that passes through vertex k.

Crowdly

Shortest paths with negative weights Assume we are running Floyd-Warshall on a g...

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