GATE Overflow Test Series | Algorithms | Test 2 | Question: 4

Question

Let $G(V, E)$ be an undirected graph with some edge weights being negative but without any negative weight cycle. Which of the following is/are TRUE when $G$ is given as input with a given source $s$? (Mark all the appropriate choices)

• A. Dijkstra's algorithm will always correctly output the shortest path to all vertices from $s$
• B. Dijkstra's algorithm will always fail to correctly output the shortest path to all vertices from $s$
• C. Bellman-Ford algorithm will always correctly output the shortest path to all vertices from $s$
• D. Bellman-Ford algorithm will always fail to correctly output the shortest path to all vertices from $s$

Comments

If the graph has negative weights, is undirected, yet has no negative weight cycles, doesn’t that imply that one of the vertices connected to the -ve edge has that edge as its only edge? In other words, one of the vertices connected to a -ve edge can only have a degree=1 to avoid -ve weight cycles. In this case, wouldn’t Dijkstra still always work?

---

@https://gateoverflow.in/user/susmit600

This thread https://stackoverflow.com/questions/6799172/negative-weights-using-dijkstras-algorithm/6799344#6799344

explains why Dijkstra might not work for all graphs with negative edge weights.

---

Option B is very interesting. In fact, DIJKSTRA may or may not work on -ve edge.

Answer 1

Dijkstra's algorithm is not designed to work for graphs with negative edges. Still, for some graphs with negative edges, it can output the correct shortest path - the cut edges being the only negative edges is an example. So, options A and B are false.
    
    Bellman-Ford algorithm will always output the correct shortest path even when the edge weights are negative as long as there is no negative weighted cycle reachable from source.