<html>
<p><img src="https://s17.postimg.org/3nkulx00f/negativeweight.jpg" width="618" height="269"/></p>
<p> Hello its a me again Drifter Programming! Today we will get into <strong>Java </strong>again talking about the already mentioned <strong>Bellman-Ford algorithm</strong> that is used for finding <strong>Single-Source Shortest Paths in Graphs</strong>. You can check out the <strong>Dijkstra </strong>algorithm for the same problem <a href="https://steemit.com/graphs/@drifter1/programming-java-graph-shortest-path-algorithm-dijkstra">here</a>! So, let's get started!</p>
<h2>Bellman-Ford Algorithm:</h2>
<p> 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 <strong>finding shortest paths when starting from a specific source vertex</strong>. The difference between those 2 algortihms is that <strong>Dijkstra doesn't work with negative weights</strong> and <strong>Bellman-Ford works and also detects negative-weight circles</strong> that make the algorithm iterate for ever and never find the best path, cause there will always be a better one.</p>
<p> Because, of this extra checking for negative-weight circles the algorithm has a slight decrease in performance when comparing it to the Dijkstra algorithm.</p>
<p><strong>So, how does the algorithm work?</strong><br>
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!</p>
<p><strong>Pseudocode </strong>from <a href="https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm#Algorithm">wikipedia</a><strong>:</strong></p>
<p><img src="https://s17.postimg.org/k7n4lpc1r/Screenshot_1.jpg" width="718" height="555"/></p>
<p> 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.</p>
<p><br></p>
<h2>Bellman-Ford Java implementation:</h2>
<p> To implement this algorithm we will use the <strong>Graph implemenation that uses Adjacency Lists</strong> (or Priority Queues) and also the<strong> Edge class</strong>/object that we used in Dijkstra. We <strong>don't need a separate Vertex </strong>class/object something that was actually not needed in Dijkstra as well, cause we can also just use the<strong> arrays with the distances and predecessors</strong>.</p>
<p>So, our<strong> classes/objects</strong> look like this:</p>
<p><strong>Edge class</strong>:</p>
<p><img src="https://s17.postimg.org/s47ltsq1b/Edge.jpg" width="495" height="661"/></p>
<p><br></p>
<p><strong>Graph class</strong>:</p>
<p><img src="https://s17.postimg.org/i6wl0r5kv/Graph.jpg" width="366" height="800"/></p>
<p><br></p>
<p>The algorithm for <strong>Bellman-Ford </strong>looks like this:</p>
<p><img src="https://s17.postimg.org/gf3m5sorz/alg.jpg" width="700" height="772"/></p>
<p><br></p>
<p>And is inside of the <strong>TestGraphs class</strong>:</p>
<p><img src="https://s17.postimg.org/dl0gsezhb/test.jpg" width="524" height="800"/></p>
<p><br></p>
<p> 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.</p>
<p>The <strong>console </strong>printed out:</p>
<p><img src="https://s17.postimg.org/yhwox17rz/console.jpg" width="355" height="414"/></p>
<p><br></p>
<p>Here the Java Codes in pastebin:</p>
<p><a href="https://pastebin.com/FMtae96K">Edge class<br>
</a><a href="https://pastebin.com/z0wNVp5X">Graph class</a></p>
<p><a href="https://pastebin.com/n5HNqPv0">TestGraphs/BellmanFord Algorithm class</a></p>
<p> 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"!</p>
<p><br></p>
<p>And this is actually it!</p>
<p> Next time in Java Graphs we will get into 2 algorthims (Floyd-Warshall and Johnson) that are used for finding all-pair shortest paths!</p>
<p>Bye!</p>
</html>
hiveblocks