MadeEasy Test Series: Algorithms - Graph Algorithms

Question

Which of the following statements is/are true?
S1: Dijkstra’s algorithm is not affected by negative edge weight cycles in the graph and gives correct shortest path.
S2: Bellman ford algorithm finds all negative edge weight cycles present in the graph.

a) Only S2

b) Only S1

c) Both S1 and S2

d) Neither S1 and nor S2

Comments

I think option A is right

Answer 1

Both are wrong . dijisktra algorithm i not affected by negative weights till there is a negative weight cycle.

bellman ford use the logic that in a graph .the shortest path contain atmost ( n-1) edges. it does not find all the cycles . and i think finding all the cycles in the graph will be exponential time because in the worst case every vertex will have a cycle . and we may have to look n vertices ( n*n)

Comments

could you please tell the bellman ford reason limited to question more clearly?

Answer 2

ans is d

in case of graph having -ve edge cycles shortest path to all the vertices .

that lies in the -ve edge cycles and reachable through the -ve edge cycles are not determined by any algorithm