This content has been marked as final.
Show 35 replies

1. Re: finding shortest path for negative weighted graph
800282 May 9, 2008 3:20 AM (in response to 843853)zion4zion wrote:
There can only be one "best" algorithm. And you haven't told what you find a better algorithm: a faster runtime, or an easier to understand algorithm. In the case of an easier to understand algorithm, BellmanFord would be a good choice.
i want to find shortest path in a negative weighted graph.
any other best algorithm than Bellman Ford algorithm ?
\\
\\Also the weight of the edge may change depending upon the traversing...
I don't know what you mean by that.
help me in this !! 
2. Re: finding shortest path for negative weighted graph
843853 May 12, 2008 1:52 AM (in response to 800282)that means, for example, if there are 10 similar type of nodes named NAME1 in a network with 50 nodes, and cost of visiting NAME1 will be the number of nodes of NAME! that are not yet traversed. 
3. Re: finding shortest path for negative weighted graph
843853 May 12, 2008 6:02 AM (in response to 843853)zion4zion wrote:
I don't know about others but I still don't understand this.
that means, for example, if there are 10 similar type of nodes named NAME1 in a network with 50 nodes, and cost of visiting NAME1 will be the number of nodes of NAME! that are not yet traversed. 
4. Re: finding shortest path for negative weighted graph
843853 May 12, 2008 9:39 AM (in response to 843853)can Bellman Ford algorithm can be used for undirected graph? 
5. Re: finding shortest path for negative weighted graph
800282 May 12, 2008 10:40 AM (in response to 843853)sabre150 wrote:
Same here.
...
I don't know about others but I still don't understand this. 
6. Re: finding shortest path for negative weighted graph
800282 May 12, 2008 10:41 AM (in response to 843853)zion4zion wrote:
Yes.
can Bellman Ford algorithm can be used for undirected graph? 
7. Re: finding shortest path for negative weighted graph
843853 May 12, 2008 11:09 AM (in response to 843853)zion4zion wrote:
An undirected graph is just a directed graph with each linked pair of nodes having a directed link in both directions.
can Bellman Ford algorithm can be used for undirected graph? 
8. Re: finding shortest path for negative weighted graph
843853 May 13, 2008 12:19 AM (in response to 843853)i have implemented Bellman Ford Algorithm, but the problem is "negative cycles". How can I overcome this ? 
9. Re: finding shortest path for negative weighted graph
843853 May 13, 2008 4:06 AM (in response to 843853)after detecting negative cycles in bellman ford algorithm, how we can eliminate that? plz help me ! 
10. Re: finding shortest path for negative weighted graph
800282 May 13, 2008 4:14 AM (in response to 843853)zion4zion wrote:
By ignoring them.
after detecting negative cycles in bellman ford algorithm, how we can eliminate that? plz help me !
Seriously, how do you expect people to answer you? You don't explain what your problem is exactly, and we have no idea if and how you implemented the algorithm. We also don't know on what data you are running it on. If you want a decent answer, please ask a specific question backed up by your algorithm and explain in detail on what graph you are running it and where your problem lies. 
11. Re: finding shortest path for negative weighted graph
843853 May 13, 2008 6:03 AM (in response to 800282)my problem is to find shortest path between a source node and a destination node, the cost of the nodes in between may be negative.
And also the cost of the node may vary. for example, if there are 5 blue nodes totally, the cost of blue node that is present first in the shortest path is 5, and the second's is 4 , the thirds is 3.....
you understood ? 
12. Re: finding shortest path for negative weighted graph
843853 May 13, 2008 6:10 AM (in response to 843853)I understand the 'negative cost' problem but as for the rest ... 
13. Re: finding shortest path for negative weighted graph
800282 May 13, 2008 6:11 AM (in response to 843853)zion4zion wrote:
No.
my problem is to find shortest path between a source node and a destination node, the cost of the nodes in between may be negative.
And also the cost of the node may vary. for example, if there are 5 blue nodes totally, the cost of blue node that is present first in the shortest path is 5, and the second's is 4 , the thirds is 3.....
you understood ?
But you said you already implemented the algorithm. Why don't you post it and explain in detail when it is failing. 
14. Re: finding shortest path for negative weighted graph
843853 May 13, 2008 6:19 AM (in response to 800282)prometheuzz 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.
But you said you already implemented the algorithm. Why don't you post it and explain in detail when it is failing.