Hello its a me again Drifter Programming! Today we will get into **Java **again talking about the already mentioned **Bellman-Ford algorithm** that is used for finding **Single-Source Shortest Paths in Graphs**. You can check out the **Dijkstra **algorithm for the same problem here! So, let's get started!

## Bellman-Ford Algorithm:

The Bellman-Ford algorithm as I already mentioned in the post about Dijkstra and also the quick introduction in the start of this post is used for **finding shortest paths when starting from a specific source vertex**. The difference between those 2 algortihms is that **Dijkstra doesn't work with negative weights** and **Bellman-Ford works and also detects negative-weight circles** that make the algorithm iterate for ever and never find the best path, cause there will always be a better one.

Because, of this extra checking for negative-weight circles the algorithm has a slight decrease in performance when comparing it to the Dijkstra algorithm.

**So, how does the algorithm work?**

Well, it's pretty similar to the Dijkstra algorithm, but iterates through all edges repeatedly. We will again store the distances and parents (or predecessors) in an array inside of the algorithm/function. We then initialize those two arrays having a value of infinity (maximum float value for us) and predecessors equal to -1 for all vertices, except the source vertex that will have a distance of 0 to itself. We then iterate through all the edges repeatedly for vertexCount - 1 times and check (as in Dijkstra) if the distance of the startingPoint u + the weight of the edge (u, v) is less than the already been set distance of the endingPoint v. If that is true then we set the new distance of v to distance of u + weight of edge (u, v) and also set u as the predecessor of v. This is the part where we might have a negative-weight circle. To check for negative-weight circle we use the same equation dist(u) + w < dist(v) and if it's true again then the graph contains a negative-weight circle, cause vertexCount - 1 iterations already gave us the shortest paths!

**Pseudocode **from wikipedia**:**

We will implement the same pseudocode, but in Java there will be some changes that we already know how to do from previous Graph Algorithms and also mentioned earlier.

## Bellman-Ford Java implementation:

To implement this algorithm we will use the **Graph implemenation that uses Adjacency Lists** (or Priority Queues) and also the** Edge class**/object that we used in Dijkstra. We **don't need a separate Vertex **class/object something that was actually not needed in Dijkstra as well, cause we can also just use the** arrays with the distances and predecessors**.

So, our** classes/objects** look like this:

**Edge class**:

**Graph class**:

The algorithm for **Bellman-Ford **looks like this:

And is inside of the **TestGraphs class**:

We ran the same graph example as with Dijkstra and got the same result and I also added a second Graph that contains a negative-weight circle and saw that the algorithm detected it.

The **console **printed out:

Here the Java Codes in pastebin:

TestGraphs/BellmanFord Algorithm class

Don't forget to remove the package declaration or you can also create and put the classes inside of a package with the name "bellmanford"!

And this is actually it!

Next time in Java Graphs we will get into 2 algorthims (Floyd-Warshall and Johnson) that are used for finding all-pair shortest paths!

Bye!