Back to Basics — Divine Algorithms Vol II: Bellman-Ford Algorithm
A Shortest Path Expedition
In the last volume of Back to Basics — Divine Algorithms, we had a more or less in-depth discussion about Edsger Wybe Dijkstra and his algorithm to find the shortest path between nodes in a graph. After I published that blog, I had some questions regarding the speed of the algorithm, if it works with every graph and more advanced ones such as “what if we have negative edge weights?” In order to address these questions all together, I decided to write about another shortest path algorithm. In this regard, we have an algorithm to compare it to. The one I found would be most convenient to show the benefits, and shortcomings, of Dijkstra’s algorithm while still showcasing a new and very interesting approach to the shortest paths between nodes in graphs, was the Bellman-Ford algorithm.
The Bellman-Ford algorithm is an algorithm that finds the shortest path in a graph from a single source vertex to all other vertices in a weighted graph. One of the defining characteristics of Bellman-Ford is that it is able to handle graphs that have negative edge weights. I will explain more about the algorithm in the following section but before that, just like the last blog, there are some extra terms we need to get familiar with in order to understand the Bellman-Ford (BF) algorithm and the subtle, yet important, differences it has in comparison to Dijkstra’s.
Is Greed a Virtue?
Greedy Algorithms. Say it with me, greedy algorithms. One last time for the people at the back, G R E E D Y. A L G O R I T H M S. Quite the important term to get familiar with. I would say that this is less of a graph term and more of an algorithm term that you will find being mentioned repeatedly if you choose to read more into the subject of algorithms. When you have a full understanding of what a greedy algorithm is, you will be able to decide whether the problem you are trying to solve would benefit more from using a greedy algorithm or not. So, what is it?
A greedy algorithm is any problem-solving heuristic that tries to find the local optimal solution at the time, hoping that at the end, these local optimal solutions will lead to a globally optimal solution. Example time. Let's say you are given a choice. You have two bags; each bag has a specific amount of money in it. One bag, bag A, has $10 and the other bag, bag B, has $100 in it. After choosing one of those bags, you are given directions to another bag with a different amount of money in it. However, there is a caveat. You are allowed to check the address in these two first bags to go see how much is in the other bags and then return back and make your choice.
In this case, there are advantages and disadvantages. If you choose to go with reading the instructions, you can go all the way there and find out that the values of the second bags were $5 and $10, meaning that you would have been better off choosing bag B and have a globally optimal profit, without having to travel at all. However, you might go to the address given by bag A and realize the bag it leads you to has $200 and the address given by bag B leads to a bag with 1$. This means that reading the address, and traveling there, actually gave you a globally optimal profit.
A greedy algorithm approach would be not reading the instructions on the paper. It would be the case where you just pick the bag with $100 in it and hoping that the second bag gives you a global optimal. The reason people go with a greedy approach is because of time efficiency. In the non-greedy approach where you check the second bag first, you spend time traveling there then traveling back to pick the bag.
The Pessimist Graph
This isn’t actually the official name of what I am about to explain, but it’s how I like to describe it. A “pessimist” graph is a graph with, wait for it, negative edge weights *BA-DUM-TSSS*. I am sorry guys, it had to be done. But anyways, as we discussed in the previous volume of this series, weighted graphs have edges with weights. But to add on top of that knowledge, it is important to know that graphs can also have edges with negative weights.
What does it mean to have an edge with a negative weight? A negative weight represents the same thing a positive edge does, just a relative value on top of an edge. But, is it a good thing to have negative edges? Well, just like positive edges, it depends on one very important thing, what is the context of your graph? You can have a weighted graph with edges that represent money spent when you take a specific route through a specific edge. In this case, a negative edge is an edge you should consider taking because it means that not only are you not spending money, but you are actually gaining money. However, if you have a graph with edges that represent the money gained, then a negative edge represents a loss in money, which makes negative edges, well, have a negative outcome.
An important concept to know, now that we know that negative edges exist, is negative cycles. In general, a cycle in a graph refers to a path where the first vertex and the last vertex of that path are the only repeated vertices. A cycle could also be referred to as a closed path. Here is an example of a cycle:
We see two cycles here:
- A → B → C → D → E → F → A
- G → H → I → J →K → L→G
In both these cases, the first and the last vertex in the path [the same vertex] is the only one repeated in that path.
Knowing that, a negative cycle is a cycle within a graph that sums up to a negative value. We will understand why this is important to the algorithm later on.
The Algorithm
I got some feedback on the last blog that the visual representations were really helpful in understanding the algorithm. So, just like Dijkstra’s algorithm blog, I will be providing steps of the algorithm, accompanied with a GIF that can aid in that explanation.
The following gif was a part of Maxim Kjaer’s blog. It is a blog that, like my blogs, goes in-depth into core computer science topics:
Something that is very important to understand about this algorithm, is that it is NOT greedy. Unlike Dijkstra, this algorithm does not simply take the local optimal solution, but it finds the global optimal solution, which does have its drawbacks. But this will be explained in the following steps:
1- If Dijkstra can, why can’t I? Just like the Dijkstra algorithm, this one starts with setting all the total cost of each node to ∞. This makes it so that any distance from one vertex to another replaces the infinity. This reduces the errors that could happen in case we set it to a number that can potentially be smaller than the total cost.
2- Relaaaaaax: The vertices are set to infinity, which makes them very stressed, hyperbolically and theoretically of course. So, the next step to do is to relax all the edges. Relaxing the edge means that the infinity edges' cost will be replaced by the cost of a newly found path. This is where we have the main difference between Dijkstra and Bellman-Ford. Dijkstra utilizes a priority queue in order to greedily relax the edges, in hopes of finding a globally optimal solution. With Bellman-Ford however, the algorithm relaxes all edges in the graph and guaranteeing the global optimal solution, but of course, taking more time than Dijkstra.
3- Spotting That Negativity: Now, this is a very, very important part of the algorithm. Because the Bellman-Ford algorithm relaxes all the edges, if the graph contains a negative cycle, the algorithm will keep going on indefinitely. That's because the graph will try and relax the edges again, finding an even more negative value. If the algorithm does not detect this, it will assume that there is always a shorter path to take and it will keep going. So, it is very important in the implementation to detect these negative cycles, in order to avoid being stuck indefinitely. After all, you don’t want to be stuck in a maze.
The Code:
In order for you guys to have a more interactive experience in the form of trying this out yourself, I have attached this example that shows how to implement Bellman-Ford using Java, Python, C++, and C#. The example showcases exactly how to write it using code, as well as testing the algorithm and providing documentation for each function. It should be a very beginner-friendly example to help you get a head start on trying it out.
Bellman-Ford vs. Dijkstra
There are two main differences between both algorithms, and they are differences I have touched upon in the blog:
1- Fast Vs. Guaranteed: As I said, Dijkstra is a greedy algorithm. It might compromise, just the slightest, on the globally optimal solution, in an attempt to accomplish the task in the fastest manner. In contrast, Bellman-Ford makes sure that the path it finds is the global optimal solution while compromising on the time it finds it. Because we are in the age of speed, most solutions tend to lean towards Dijkstra’s algorithm or any greedy algorithm in that case. However, if the optimal time is not the highest priority, Bellman-Ford is one of the better shortest path algorithms you can use
2- Negativities: Dijkstra’s algorithm is not equipped to handle negative edges or deal with negative cycles. This is where Bellman-Ford shines within this comparison. If you have a use case where time is an extremely high priority, but it contains negative weights, you cannot use Dijkstra because of this specific limitation. BF, on the other hand, does know how to handle it. But, handling negative weights is not the only upside of BF. Many algorithms fail due to the fact that they can handle negative weights but cannot detect negative cycles. With Bellman-Ford, this should not be an issue if it is implemented correctly.
Usually, at this point, I would have a new section that outlines the use cases of the algorithm. However, I will not be doing that here. The reason being that both algorithms have very similar use cases, if you need a refresher on them, see the previous blog. What I will do in this blog is to list the things you need to put into consideration, in order to understand which algorithm is better to use:
1- Is it time-sensitive? Dijkstra ✅ Bellman-Ford ❌
2- Do you need the best solution? Dijkstra ❌ Bellman-Ford ✅
3- Does it have negative weights? Dijkstra ❌ ❌ Bellman-Ford ✅✅✅✅✅
Now What?
Now that you have enriched your graph theory knowledge with new terms, and your algorithm knowledge with new ways of solving new problems, try it out. Use the code I attached for the Bellman-Ford algorithm and try to test it and maybe find out more limitations. As usual, if there are any questions you have, you can contact me.
I hope you guys like this volume of Back to Basics — Divine Algorithms. If you do, please give me feedback, ideas, really anything that will help you enjoy reading this series more. Also, as usual, I left a hint in the blog on what I will be talking about next! Enjoy!
