Menu
Does Prim's? Solution: Yes, both algorithms work with negative edge weights because the cut property still applies.
Their correctness is not affected by the negative weight edges. In Kruskal's algorithm the safe edge added to A (subset of a MST) is always a least weight edge in the graph that connects two distinct components. So, if there are negative weight edges they will not affect the evolution of the algorithm.
Since Dijkstra's goal is to find the optimal path (not just any path), it, by definition, cannot work with negative weights, since it cannot find the optimal path. Dijkstra will actually not loop, since it keeps a list of nodes that it has visited.
The best-known algorithm for finding single-source shortest paths in a directed graph with negative edge weights is the Bellman-Ford algorithm.
Yes, you are right. The concept of MST allows weights of an arbitrary sign. The two most popular algorithms for finding MST (Kruskal's and Prim's) work fine with negative edges.
Actually, you can just add a big positive constant to all the edges of your graph, making all the edges positive. The MST (as a subset of edges) will remain the same.
Yes, you are right because if you see the algorithm for shortest path like dijkstera it will check if the present distance of vertex v is greater than sum of present value + edge weight then it will change the value of distance of vertex v from s by the sum value and if the edge weight is negative then it will give some problems.
But in the MST problem there are algorithms like prims,kruskal which take only the minimum weight edge so that make the negative edge qualify for MST.
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