hard20 pts · first answer countsgraphsshortest-path

All pairs on a sparse graph with negative edges

A sparse graph with 10,000 vertices has some negative edges but no negative cycles. You need all-pairs shortest paths. Which approach fits best?

A.Floyd-Warshall, about 10^12 steps, as it is the only optionB.Dijkstra from each vertex on the original weightsC.Johnson’s: Bellman-Ford once to reweight, then Dijkstra from each vertexD.Add a constant to all weights, then Dijkstra from each vertex

Discussion 0

Join free to post in the discussion.

All pairs on a sparse graph with negative edges

Discussion 0

Related questions