1 2 3 Previous Next 35 Replies Latest reply on Jun 8, 2010 7:31 AM by PhHein

# finding shortest path for negative weighted graph

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...

help me in this !!
• ###### 1. Re: finding shortest path for negative weighted graph
zion4zion wrote:
i want to find shortest path in a negative weighted graph.

any other best algorithm than Bellman Ford algorithm ?
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, Bellman-Ford would be a good choice.
\\
\\
Also the weight of the edge may change depending upon the traversing...

help me in this !!
I don't know what you mean by that.
• ###### 2. Re: finding shortest path for negative weighted graph
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
zion4zion wrote:
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.
I don't know about others but I still don't understand this.
• ###### 4. Re: finding shortest path for negative weighted graph
can Bellman Ford algorithm can be used for undirected graph?
• ###### 5. Re: finding shortest path for negative weighted graph
sabre150 wrote:
...
I don't know about others but I still don't understand this.
Same here.
• ###### 6. Re: finding shortest path for negative weighted graph
zion4zion wrote:
can Bellman Ford algorithm can be used for undirected graph?
Yes.
• ###### 7. Re: finding shortest path for negative weighted graph
zion4zion wrote:
can Bellman Ford algorithm can be used for undirected graph?
An undirected graph is just a directed graph with each linked pair of nodes having a directed link in both directions.
• ###### 8. Re: finding shortest path for negative weighted graph
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
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
zion4zion wrote:
after detecting negative cycles in bellman ford algorithm, how we can eliminate that? plz help me !
By ignoring them.
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
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
I understand the 'negative cost' problem but as for the rest ...
• ###### 13. Re: finding shortest path for negative weighted graph
zion4zion wrote:
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 ?
No.

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
prometheuzz wrote:
But you said you already implemented the algorithm. Why don't you post it and explain in detail when it is failing.
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.
1 2 3 Previous Next