hard20 pts · first answer countsgraphsshortest-path

Making all weights positive by adding a constant

To remove negative weights, a developer adds the same constant c to every edge, then runs Dijkstra. Why can this give the wrong path?

A.Adding a constant can create new negative cyclesB.Dijkstra cannot handle edge weights above 100C.Paths with more edges gain more, so the best path can changeD.The new graph may become disconnected from the source

Discussion 0

Join free to post in the discussion.

Making all weights positive by adding a constant

Discussion 0

Related questions