This content has been marked as final.
Show 35 replies

15. Re: finding shortest path for negative weighted graph
843853 May 13, 2008 11:22 AM (in response to 800282)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.
i have pasted the link
http://en.wikipedia.org/wiki/BellmanFord_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
800282 May 13, 2008 11:23 AM (in response to 843853)sabre150 wrote:
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.
...
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. 
17. Re: finding shortest path for negative weighted graph
843853 May 13, 2008 11:25 AM (in response to 843853)I'm now even more lost. What has this to do with 'blue' nodes? 
18. Re: finding shortest path for negative weighted graph
800282 May 13, 2008 11:27 AM (in response to 843853)zion4zion wrote:
How does your graph look like exactly? (can you post an adjacency matrix of it? or an asciidrawing?)
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.
i have pasted the link
http://en.wikipedia.org/wiki/BellmanFord_algorithm
See i want a solution for the problem, not only by Bellman Ford algorithm, any other solution too....
What path in that graph are you looking for? 
19. Re: finding shortest path for negative weighted graph
843853 May 13, 2008 11:57 AM (in response to 800282)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
843853 May 13, 2008 12:30 PM (in response to 843853)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
843853 May 13, 2008 12:36 PM (in response to 843853)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
800282 May 13, 2008 4:03 PM (in response to 843853)zion4zion wrote:
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.
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 ?
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
843853 May 13, 2008 4:24 PM (in response to 800282)prometheuzz wrote:
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.
And why do you say "negative cycles", I assume you are also not interested in "positive cycles", correct? 
24. Re: finding shortest path for negative weighted graph
800282 May 13, 2008 7:43 PM (in response to 843853)sabre150 wrote:
You will not be ignored that easily!
...
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.
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
843853 May 14, 2008 4:41 AM (in response to 800282)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
843853 May 14, 2008 5:25 AM (in response to 843853)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
843853 May 14, 2008 5:49 AM (in response to 843853)by keep tracking we can stop the cycle, i want to reach the source ... 
28. Re: finding shortest path for negative weighted graph
843853 May 14, 2008 5:53 AM (in response to 843853)zion4zion wrote:
Are you [the Architecthttp://en.wikipedia.org/wiki/Architect_%28The_Matrix%29]?
by keep tracking we can stop the cycle, i want to reach the source ... 
29. Re: finding shortest path for negative weighted graph
843853 May 14, 2008 6:15 AM (in response to 843853)what u mean exactly?