1
$\begingroup$

The Dijkstra's algorithm is never used for a graph with a negative weight. The following graph has negative weight but when the Dijkstra's single source shortest path algorithm run from vertex a, it computes the correct shortest path distance to all the vertices.

enter image description here

But when I solve it for the following graph: enter image description here

I am not getting a shortest path, why does the Dijkstra's algorithm working for the first graph and not the other one, or did I make any mistake? Could anyone make me understand it? Run Dijkstra’s algorithm on the graph below considering D as the source vertex, it would make this easier to understand if you also describe the status of the distance array at each iteration.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

In the second graph, we can replace each undirected edge with two directed edges. For example we can replace edge between D,C with a directed edge $D\to C$ and directed edge $C\to D$ such that each edge weight is equal to $-8$. This means we have a reachable negative cycle from source, so there is no algorithm to compute shortest path in a such instance of shortest path problem. Because, for example
$d[D]=-\infty$.

Improve this answer
$\endgroup$
1
$\begingroup$

The first graph is a directed graph with no negative cycles.

However, the second graph is an undirected graph that has a negative cycle. This means that there is no shortest path, since we can always walk any number of times we want in that negative cycle - which will just continue to decrease the path's cost.

Essentially this means you tried to compare two things that cannot be compared: one with a valid shortest path, and one without it.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.