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.
zion4zion wrote:How does your graph look like exactly? (can you post an adjacency matrix of it? or an ascii-drawing?)
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/Bellman-Ford_algorithm
See i want a solution for the problem, not only by Bellman Ford algorithm, any other solution too....
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 ?
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?
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).
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
zion4zion wrote:Are you [the Architect|http://en.wikipedia.org/wiki/Architect_%28The_Matrix%29]?
by keep tracking we can stop the cycle, i want to reach the source ...