I was doing some reading on the algorithms used in link state vs. distance vector routing protocols. I understand that Dijkstra's algorithm is used in link state routing, and I can see why this would be so. But I've also read that the Bellman-Ford algorithm is more useful for distance vector routing because it can work with negative edge weights? I'm confused by this. How can you have a negative edge weight in a real network? My understanding is that the edge weight corresponds to the estimated time it takes for a packet to make its way between one router and the next. How can this value be negative?

  • What, exactly, were you reading? It's helpful to know the context of your question. – Ron Trunk Sep 12 '16 at 13:24
  • quora.com/… – user628544 Sep 12 '16 at 13:25

Negative edge weights are indeed not very useful in routing applications of the algorithm. Being able to handle negative weights is one property in which Bellman-Ford differs from Dijkstra, but it is not the reason it is preferred in Distance Vector algorithms.

Running Dijkstra's algorithm requires full knowledge of all edges and weights in the network. Unlike link state routing algorithms, distance vector algorithms do not construct such a full network map.

This means Dijkstra's algorithm cannot be used in distance vector algorithms. (Distributed) Bellman-Ford works without the full network view and thus can be used in distance vector algorithms.

| improve this answer | |

I think you're misreading/misinterpreting the article. It doesn't say BF is better for routing because it works with negative weights, that's just a feature of the mathematical algorithm. As you point out, in "real life," negative weights don't exist. But neither do imaginary numbers, yet you can do math with them.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.