Bellman-Ford Algorithm Visually Explained

Dino Cajic
Jul 8 · 8 min read
Image for post
Image for post

The Bellman-Ford algorithm finds the shortest path to each vertex in the directed graph from the source vertex. Unlike Dijkstra’s algorithm, Bellman-Ford can have negative edges.

Image for post
Image for post

To begin, all the outbound edges are recorded in a table in alphabetical order.

Image for post
Image for post

Like Dijkstra’s algorithm, a table recording the distance to each vertex and the predecessor of each vertex is created. The distances for each vertex, except the source vertex, is initialized to infinity. Distance is represented by the variable d and the predecessor is represented by the variable π.

Image for post
Image for post

The Bellman-Ford algorithm will iterate through each of the edges. Since there are 9 edges, there will be up to 9 iterations. During each iteration, the specific edge is relaxed. During the first iteration, the cost to get to vertex C from A is -3. The current distance from the source to A is infinity. When -3 is added to infinity, the result is infinity, so the value of C remains infinity. Similarly, from A to E, the cost is 2, however, since the distance to A is infinity, the value of E remains infinity. Looking at edges B-F, C-B, C-H, F-G, G-B, and H-D, we can see that they all yield the same result, infinity. The last edge, S-A, yields a different result. The weight of edge S-A is 5. The current distance to S is 0, so the distance from S to A is 0 + 5 = 5. The predecessor to A is set to S. After the first iteration, Bellman-Ford found the path to A from S.

Image for post
Image for post

Since all the edges have been relaxed, Bellman-Ford starts on the second iteration. Although each edge is relaxed, the only edges that matter are the edges from S and from A since the distance to those vertices is already known. The distance to all other vertices is infinity. Looking at the table containing the edges, we start by relaxing edge A-C.

Image for post
Image for post

The weight of edge A-C is -3. The current distance to vertex A is 5 via edge S-A, so the distance to vertex C is 5 + (-3) = 2. The predecessor of C is A. The weight of edge A-E is 2. The distance to E is 5 + 2 = 7 via edge S-A. The predecessor of E is updated to A. Edge B-F cannot be relaxed yet.

Image for post
Image for post

Edge C-B can be relaxed since we know the distance to C. The distance to B is
2 + 7 = 9 and the predecessor of vertex B is C. Edge C-H can be relaxed since we know the distance to C. The distance to H is 2 + (-3) = -1 and the predecessor of vertex H is vertex C.

Image for post
Image for post

Edge F-G cannot yet be relaxed. Edge G-B cannot be relaxed. Edge H-D can be relaxed since we know the distance to vertex H is -1. The distance to vertex D is -1 + 1 = 0 and the predecessor to vertex D is vertex H.

Image for post
Image for post

The distance to A from edge S-A is already 5 so no update is necessary. This ends iteration 2.

Image for post
Image for post
Image for post
Image for post

During the third iteration, the Bellman-Ford algorithm examines all the edges again. Edges A-C and A-E yield the same results. Edge B-F can now be relaxed. The distance to B is 9, so the distance to vertex F is 9 + (-5) = 4. The predecessor to F is B.

Image for post
Image for post

Edges C-B and C-H yield the same results, so the table remains the same. Edge F-G can now be relaxed. The distance to vertex F is 4, so the distance to vertex G is 4 + 2 = 6. The predecessor of G is F.

Image for post
Image for post

Edge G-B can now be relaxed. The distance to vertex G is 6, so the distance to B is 6 + 4 = 10. Since vertex B can be reached with a shorter distance by going through edge C-B, the table remains the same.

Image for post
Image for post
Image for post
Image for post

During the fourth iteration, all the edges are examined. The algorithm sees that there are no changes, so the algorithm ends on the fourth iteration.

If this graph had a negative cycle, after the iteration is repeated n-1 times, theoretically the Bellman-Ford algorithm should have found the shortest paths to all vertices. During the nth iteration, where n represents the number of vertices, if there is a negative cycle, the distance to at least one vertex will change. Let’s look at a quick example.

Image for post
Image for post
Image for post
Image for post

The table with the distances and the predecessors is constructed. The distances are initialized to infinity for vertices A, B and C. The distance to S is 0.

Image for post
Image for post

Looking at the first edge, A-B cannot be relaxed yet and neither can edge B-C nor edge C-A. Edge S-A can be relaxed. The distance to S is 0, so the distance to A is 0 + 3 = 3. The predecessor of A is S.

Image for post
Image for post

Edge S-B can also be relaxed. The distance to vertex B is 0 + 6 = 6. Vertex B’s predecessor is S.

Image for post
Image for post

The first iteration is complete. During the second iteration, all of the edges are examined again.

Image for post
Image for post

Edge A-B can be relaxed during the second iteration. The distance to A is 3, so the distance to vertex B is 3 + 5 = 8. Since the distance to B is already less than the new value, the value of B is retained. Edge B-C can be reached in 6 + 2 = 8. Vertex C’s predecessor is vertex B.

Image for post
Image for post
Image for post
Image for post

Edge C-A is examined next. The distance to C is 8 units, so the distance to A via edge B-C is 8 + (-10) = -2. Since the distance to A via edge C-A is less than the distance to A via S-A, the distance to A is updated.

Image for post
Image for post
Image for post
Image for post

Edges S-A and S-B yield nothing better, so the second iteration is complete. The third iteration starts.

Image for post
Image for post

Edge A-B is relaxed. The distance to A is currently -2, so the distance to B via edge A-B is -2 + 5 = 3. Since the distance to B is less via A-B than S-B, the distance is updated to 3. Vertex B’s predecessor is updated to vertex A.

Image for post
Image for post

Edge B-C is relaxed next. The current distance to B is 3, so the distance to C is
3 + 2 = 5. The distance to C is updated to 5.

Image for post
Image for post

Edge C-A is relaxed. The distance to C is 5 + (-10) = -5. The distance to vertex A is updated to -5 units.

Image for post
Image for post

Edges S-A and S-B yield no better results. At this time, all shortest paths should have been found. If we examine another iteration, there should be no changes.

Image for post
Image for post

Edge A-B is relaxed. The distance to A is -5 so the distance to B is -5 + 5 = 0. The distance to B is updated to 0. Since the value changes on the nth iteration, values will change on the n+1th iteration as well; values will continue to change indefinitely. If we examine the graph closely, we can see that A-B-C yields a negative value: 5 + 2 + (-10) = -3.


If you liked what you read, check out my book, An Illustrative Introduction to Algorithms.

Dev Genius

Coding, Tutorials, News, UX, UI and much more related to development

Sign up for Best Stories

By Dev Genius

The best stories sent monthly to your email. Take a look

By signing up, you will create a Medium account if you don’t already have one. Review our Privacy Policy for more information about our privacy practices.

Check your inbox
Medium sent you an email at to complete your subscription.

Dino Cajic

Written by

Author of An Illustrative Introduction to Algorithms. A Software Engineer with a B.S. in Computer Science, a minor in Biology, and a passion for learning.

Dev Genius

Coding, Tutorials, News, UX, UI and much more related to development

Dino Cajic

Written by

Author of An Illustrative Introduction to Algorithms. A Software Engineer with a B.S. in Computer Science, a minor in Biology, and a passion for learning.

Dev Genius

Coding, Tutorials, News, UX, UI and much more related to development

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch

Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore

Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store