Bellman Ford Algorithm

Sep 16, 2019 19:08 · 217 words · 2 minute read

For my computer networking class, I’ve been tasked (for project 3) with implementing the Bellman-Ford algorithm, a distance vector algorithm used for identifying the shortest path between nodes. What’s interesting about the project is that we are implementing the Bellman-Ford algorithm in a distributed, asynchronous fashion: each node receives message updates sent from its directly connected neighbors, who send their own distance vectors. In other words, each node constructs its world view and incrementally updates its world view as additional messages are received.

Today, I was able to finalize the project and I’m so relieved because over the weekend, I found myself getting frustrated since my code was failing on some edge cases. More specifically, topologies containing negative valued edges were triggering pathological behavior in my implementation: my code would loop forever and never terminate. But fortunately today, I stumbled across some Piazza posts, where I found other students reporting the same issue as I was and luckily, one of the other students replied, pointing out that we probably failed to handle a certain edge case that was called out in the project directions. And they were right because after I made a minor modification to my code, literally a single line, my algorithm starting passing all the (student provided) test cases, which was such a relief!