In the Bellman–Ford algorithm, what is the practical meaning of having a negative path between routers? I have tried searching the net but didn't find any data
thanks Eli
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
In the context of network routing, negative-weight edges are meaningless.
Bellman–Ford is just an algorithm for finding lowest-cost paths in a weighted graph. The algorithm itself doesn't know or care what the vertices, edges and weights mean: it just finds paths. Interpreting those paths is for the user.
answered Dec 11, 2014 at 22:34
$\begingroup$
$\endgroup$
It depends on the innterpretation of the graph, not the algorithm. For example, if you have a deck of cards and have a graph to represent possible exchanges, the weights of the vertices may mean the price you need to pay to exchange. In such case, negative weight of a route between some nodes would mean you are paid more than you pay for such a chain of exchanges.
The algorithm is just to find the shortest paths, it has nothing to do with the interpretation of your graph. What you may mean is that another popular shortest-paths algorithm, which is Dijkstra's, can not handle negative weights, and Bellman-Ford can (it will not hang or return incorrect values). But still this is a separate topic from the interpretation of negative path weights.
