Shortest paths with negative weights Assume that we have a graph with a negative cycle that is reachable from the source s. For which vertices is “the shortest distance from s” not a well-defined number?

Question

Accepted Answer

Every vertex reachable FROM the cycle, because going round the cycle again always makes the total smaller.

Answer

Every vertex in the graph, whether or not the cycle can reach it.

Answer

None of them: the distances are still well defined, but Bellman-Ford cannot find them.

Answer

Only the vertices on the cycle itself.

Answer

Only the vertices from which the cycle can be reached.

Crowdly

Shortest paths with negative weights Assume that we have a graph with a negative...

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