Question

Usually, Djikstra’s shortest-path algorithm is not used on graphs with negative-weight edges because it may fail and give us an incorrect answer. However, sometimes Djikstra’s will give us the correct answer even if the graph has negative edges.
You are given graph G with at least one negative edge, and a source s. Write an algorithm that tests whether Djikstra’s algorithm will give the correct shortest paths from s. If it does, return the shortest paths. If not, return ‘no.’ The time complexity should not be longer than that of Djiksta’s algorithm itself, which is Θ(|E| + |V | log |V |).
(Hint: First, use Djikstra’s algorithm to come up with candidate paths. Then, write an algorithm to verify whether they are in fact the shortest paths from s.)

Answer 1