Dijkstra algo vs bellman

#1

i think that dijkstra algo if implemented using a set will be able to handle negative weight edges(which doesnt lead to cycle)…
but in ur videos of bellman ford the example u gave to prove that dijkstra wil fail in negative edges gives the correct output even by dijkstra using a set…

am i right??

#2

Plz reply at the earliest

#3

Just because the dijstra works for this case, does not mean that it works for every case. it might just be happening that two negatives cancelled each other to create a positive.
here is a proof of why dijikstra does not work for that

Recall that in Dijkstra’s algorithm, once a vertex is marked as “closed” (and out of the open set) - the algorithm found the shortest path to it , and will never have to develop this node again - it assumes the path developed to this path is the shortest.

But with negative weights - it might not be true. For example:

       A
      / \
     /   \
    /     \
   5       2
  /         \
  B--(-10)-->C

V={A,B,C} ; E = {(A,C,2), (A,B,5), (B,C,-10)}

Dijkstra from A will first develop C, and will later fail to find A->B->C

Note that this is important, because in each relaxation step, the algorithm assumes the “cost” to the “closed” nodes is indeed minimal, and thus the node that will next be selected is also minimal.

The idea of it is: If we have a vertex in open such that its cost is minimal - by adding any positive number to any vertex - the minimality will never change.
Without the constraint on positive numbers - the above assumption is not true.

Since we do “know” each vertex which was “closed” is minimal - we can safely do the relaxation step - without “looking back”. If we do need to “look back” - Bellman-Ford offers a recursive-like (DP) solution of doing so.

As for working with set, remember that Dijkstra is a greedy algorithm, meaning we assume that we have made the best choice possible in every step of the algorithm. With negative edges, this is no longer possible and thus a greedy algorithm will not suffice, even if we store the values in a set

#4

Just because the dijstra works for this case, does not mean that it works for every case. it might just be happening that two negatives cancelled each other to create a positive.
here is a proof of why dijikstra does not work for that

But in my example there is only 1 negative value…
So hoe is this point valid … explain
And I am using set approach…not the priority queue…

#5

By two negative it created positive I meant that two incorrect subparts merged to create a positive subpart.
Ex
Suppose someone created square function and used the + operator instead of *. he then tested it with a input value of 2.
Even though the logic is incorrect, he still got the right answer.
The same is happening with this case. Try using the test case given above.
As for the set part, I have written about that too in the end. Read it fully

#6

i have given it the input that u gave …it still shows correct ans …check it …
in set we dont close a node by marking it visited like in priority queue.(.and then never come across it…)…
therefore i think dijkstra with set will work…in the case of negative edges…which dont form a cycle

plz reply at the earliest with proper explaination
even if u put the example given on geeks for geeks for bellman algo in my code carefully,
it gives
the same ans …

#7

atleast reply and clear the doubts properly…at the earliest now plz

#8

Bro if you modify dijkstra like this it isnt dijkstra anymore.
This is a different algorithm
You are not closing the node which is a fundamental of dijkstra as it is greedy algorithm.
Even sort functions can have a O(N) time complexity if used with a hashmap but it is not a sort function then.
This what you have done is an advanced concept of algorithms called amortized analysis of functions where we modify the algorithms based on perceived input and conditions to perform better than plain algorithms.

#9

I would also like you to once consult with your course instructor regarding this as if someone has not done this before, you can actually publish a paper over this.

#10

I have not modified anything…I have seen the video of Prateek bhaiya …which he has implemented Dijkstra using a set…u can also look at it and plz clear my doubt…

#11

Okay I will see the video
Anything else comes up I will discuss via chat option
You can close the doubt now

#12

But my doubt isnt resolved why will I close it…clear my doubt first…
U don’t jnow Dijkstra using set???

#13

Here call me 7838702561 so that I can resolve your doubt

#14

Now listen the thing is that I personally have never used dijkstra with a set before.

This is your doubt, well more of an inquiry since you want to ask whether this method will also work or not. It not a doubt as in help required or code not working. Its that you believe that dijkstra with a set can be used in place of bellman ford.

However note that in the bellman video the dijkstra that was shown to fail for negative edges was the typical one and not with a set. So now we can go two places from here:-

  1. Dijkstra with a set can really be a substitute for bellman. However this is highly unlikely as I did not come up with even a single resource on the internet claiming so. Also if so can be done then bellman would not had been developed in the first place.

  2. The dijkstra with a set has not properly been tested enough. Try testing it with multiple negative edges, same value edges, edges with zero weight, non optimal paths etc. It could be that all the test cases that you have executed till now are giving you false positive.

P.S during the video in which dijkstra with a set is being discussed, was it mentioned that it could be used in place of bellman? Or was the bellman video different from the dikjkstra with a set video? It would be helpful if you could forward me the video also as then I can also understand better this concept