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?
Bellman-Ford Algorithm – How Does Bellman-Ford Algorithm Apply to Real Networks?
routing
Best Answer
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.