Menu
Will Dijkstra's Algorithm work if the digraph has only one negative weight edge and does not contain negative weight cycles?
257
Dijkstra's algorithm solves the shortest-path problem for any weighted, directed graph with non-negative weights. It can handle graphs consisting of cycles, but negative weights will cause this algorithm to produce incorrect results.
Since Dijkstra follows a Greedy Approach, once a node is marked as visited it cannot be reconsidered even if there is another path with less cost or distance. This issue arises only if there exists a negative weight or edge in the graph.
Requirements. Dijkstra's Algorithm can only work with graphs that have positive weights. This is because, during the process, the weights of the edges have to be added to find the shortest path. If there is a negative weight in the graph, then the algorithm will not work properly.
No. Dijkstra's algorithm is greedy. It assumes path weights are strictly increasing.
Consider the following graph. S→A→E is optimal, but the Dijkstra's will return S→B→E.
167
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
