1 2 3 35 Replies Latest reply on Jun 8, 2010 7:31 AM by PhHein Go to original post
• ###### 15. Re: finding shortest path for negative weighted graph
I have implemented bellman ford algorithm for this. Bellman Ford algorithm wont work if the graph have negative cycles. I want to overcome this problem in any means. you can refer the wikipedia "Bellman ford algorithm" for the source code. There it is implemented in C. i dont want to put the code here since i have some other problems.

http://en.wikipedia.org/wiki/Bellman-Ford_algorithm

See i want a solution for the problem, not only by Bellman Ford algorithm, any other solution too....
• ###### 16. Re: finding shortest path for negative weighted graph
sabre150 wrote:
...
I suspect it is not failing, I suspect it is just not doing what the OP wants. I still don't understand what the OP wants.
Yes, that might be the case. That's why I hoped the OP would put a bit more effort in his/her explanation. Alas for the OP.
• ###### 17. Re: finding shortest path for negative weighted graph
I'm now even more lost. What has this to do with 'blue' nodes?
• ###### 18. Re: finding shortest path for negative weighted graph
zion4zion wrote:
I have implemented bellman ford algorithm for this. Bellman Ford algorithm wont work if the graph have negative cycles. I want to overcome this problem in any means. you can refer the wikipedia "Bellman ford algorithm" for the source code. There it is implemented in C. i dont want to put the code here since i have some other problems.

http://en.wikipedia.org/wiki/Bellman-Ford_algorithm

See i want a solution for the problem, not only by Bellman Ford algorithm, any other solution too....
How does your graph look like exactly? (can you post an adjacency matrix of it? or an ascii-drawing?)
What path in that graph are you looking for?
• ###### 19. Re: finding shortest path for negative weighted graph
0 - Black // This is integer Zero
W -White
B- Blue
P - Pink
Y - Yellow
G- Green
R- Red

R 0 W 0 W W W W W W
0 W 0 0 W W W W W W
Y 0 P 0 W W W 0 W W
W W 0 P W W W 0 W W
W 0 W W W 0 0 0 W 0
W 0 W W 0 W W W 0 W
W W 0 0 0 W W 0 W W
W 0 W W B W 0 W W W
0 B 0 W W W W 0 W W
W W W 0 W W W W W G

this is my graph.
red is the source and green is the destination. Black should not be visited.

Costs

w 1
B Weight equals Total number of Blue cells which are not yet traversed.
y Weight equals Total number of Yellow cells which are not yet traversed
p -4(negative)
• ###### 20. Re: finding shortest path for negative weighted graph
I don't think the dynamic nature of the link cost makes this suitable for any of the 'fixed' cost algorithms. It might work for a particular matrix but then for a different matrix may not. I could be wrong.
• ###### 21. Re: finding shortest path for negative weighted graph
u r correct sabre.

ther is no direct algoritm ...

but i want to implement atleast without the dynamic change of cost.
assume b=4 and y=3

if we use bellman ford algorithm "negative cycles" is the problem. how to overcome this ?
• ###### 22. Re: finding shortest path for negative weighted graph
zion4zion wrote:
u r correct sabre.

ther is no direct algoritm ...

but i want to implement atleast without the dynamic change of cost.
assume b=4 and y=3

if we use bellman ford algorithm "negative cycles" is the problem. how to overcome this ?
I don't understand what the problem exactly is. You don't want cycles? Fine, just keep track of a set of already visited vertices and don't visit a vertex twice.
And why do you say "negative cycles", I assume you are also not interested in "positive cycles", correct?
• ###### 23. Re: finding shortest path for negative weighted graph
prometheuzz wrote:
And why do you say "negative cycles", I assume you are also not interested in "positive cycles", correct?
Ignore this if I am stating the obvious but if one has a "negative cycle" then one can keep going round and round and round the cycle with forever reducing cost. If one has "positive cycles" then the cost just increases. Since one is trying to get minimum cost paths then if they can be allowed then obviously "negative cycles" are good. As you say, the OP has just to mark a link as having been traversed and then not allow this to be traversed more than once.
• ###### 24. Re: finding shortest path for negative weighted graph
sabre150 wrote:
...
Ignore this if I am stating the obvious
You will not be ignored that easily!
; )

but if one has a "negative cycle" then one can keep going round and round and round the cycle with forever reducing cost. If one has "positive cycles" then the cost just increases. Since one is trying to get minimum cost paths then if they can be allowed then obviously "negative cycles" are good. As you say, the OP has just to mark a link as having been traversed and then not allow this to be traversed more than once.
To be honest, I was (or am) a bit confused by the OP: s/he considers the fact that such negative cycles can occur, but does not see the (IMO) easy answer to keep track of a set of already visited nodes (or flag nodes as visited).
Also, if the graph is large enough, positive cycles will most probably also occur while polling some sort of priority queue with all the paths in it. And since the OP specifically said "negative cycles" I assumed s/he dismissed the positive cycles.
• ###### 25. Re: finding shortest path for negative weighted graph
if ther exist a negative cycle we cannot reach the source from destination. since the cycle becomes a infinite cycle. i want to avoid this
• ###### 26. Re: finding shortest path for negative weighted graph
zion4zion wrote:
if ther exist a negative cycle we cannot reach the source from destination. since the cycle becomes a infinite cycle. i want to avoid this
:|

Here's a wild and crazy (and very novel) idea.

Why don't you keep track of a set of already visited nodes? Or flag nodes as visited?
• ###### 27. Re: finding shortest path for negative weighted graph
by keep tracking we can stop the cycle, i want to reach the source ...
• ###### 28. Re: finding shortest path for negative weighted graph
zion4zion wrote:
by keep tracking we can stop the cycle, i want to reach the source ...
Are you [the Architect|http://en.wikipedia.org/wiki/Architect_%28The_Matrix%29]?
• ###### 29. Re: finding shortest path for negative weighted graph
what u mean exactly?
1 2 3