This discussion is archived
1 2 3 Previous Next 35 Replies Latest reply: May 12, 2008 8:40 AM by 800282 Go to original post
• ###### 30. Re: finding shortest path for negative weighted graph
Currently Being Moderated
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
Currently Being Moderated
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
Currently Being Moderated
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
Currently Being Moderated
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
Currently Being Moderated
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
Currently Being Moderated
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.