'Dijkstra Algorithm = SSSP

enter image description here

What i have learnt , that dijkstra cannot work with negative edge weights . For that we have to use bellman ford .

Bellman fords works well with negative edge weights and negative cycles , which are not reachable from source otherwise, it will return a msg "Negative cycles exist".

But, this graph shown above works well with dijkstra , even though negative edge weights exist. So, how to know when to use dijkstra with negative edge weights ??

What is think , is that dijkstra can or cannot work with negative weight edges. If negative cycle exists, then it will not work. But if not exists, it can or cannot work.

Am i right ?? plz guide me for this ??

algorithmdijkstra


Solution 1:[1]

Dijkstra cannot work with negative weight edges. There is a algotithm named Johnson, which "re-weight" all the edges in the graph and finally make all the edges be positive. But the algorithm call the bellman ford algorithm and time complexity of it is O(V2logV + VE). So the time complexity of Dijkstra + Johnson is not good. But if the graph can be processed, maybe you can use the algorithm in advance. PS: I'm sorry for my poor English.

Solution 2:[2]

check the following code

    import networkx as nx
    g = nx.Graph()
    g.add_edge(1, 2, weigbt=-10)
    g.add_edge(2, 3, weight = -5)
    g.add_edge(1, 3, weight =-6)
    print(nx.single_source_dijkstra(g, 1, 3))

it doesn't matter if all of your edges are positive or negative, the Dijkstra SSSP will give you the same answer. HOWEVER, it doesn't mean that for any graph with negative edge, the Dijkstra shortest path MAY give right answer in case of negative edge but that doesn't mean it WILL give right answer.

Solution 3:[3]

You are right, Dijkstra will work for negative weights. However it won't work if sum of weights in any cycle is negative.

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 qifeng
Solution 2 darya life
Solution 3 Jacek

Related Questions