1 2 3 Previous Next 35 Replies Latest reply on Jun 8, 2010 7:31 AM by PhHein Go to original post
• ###### 30. Re: finding shortest path for negative weighted graph
zion4zion wrote:
what u mean exactly?
You make him remind of the guy in the chair in the following clip: [http://www.youtube.com/watch?v=Ra5-H9ZBS1U]
• ###### 31. Re: finding shortest path for negative weighted graph
I have solved the problem.
I used Dijkstra's algoritm itself but i added some conditions.

In the dijktra's algorithm, after settling a node it wont take that node again in the openlist, but added that.
But i didnt took the node that is already present in the path.....

and hence solved the problem.

thank u all.
• ###### 32. Re: finding shortest path for negative weighted graph
hi,
what i do not understand is how u managed to handle negative weights with dijkstra?
or I am confused ?
thanks
• ###### 33. Re: finding shortest path for negative weighted graph
Often it's sufficient to find the most negative weight, and subtract that value from all the weights, so the minimum weight is zero.
• ###### 34. Re: finding shortest path for negative weighted graph
If a negative weighted cycle is in the graph then finding a shortest path is not possible....
• ###### 35. Re: finding shortest path for negative weighted graph
Welcome to the forum. Please don't post in threads that are long dead and don't hijack other threads. When you have a question, start your own topic. Feel free to provide a link to an old post that may be relevant to your problem.