Bellman-Ford Algorithm in PHP Tutorial

Udemy Generic 728x90

Objective

In this tutorial we are going to learn, how bellman-ford algorithm works in PHP

 

Bellman-ford algorithm used to find the shortest distance between single source to all other vertices in weighted directed graph. It allow negative edge weight and can detect negative cycles in a graph. This algorithm is developed by Richard Bellman and Lester Ford Jr. in 1958.

Step 2

Data Structure – graph

A graph data structure consists of a finite (alterable) set of ordered pairs, called edges or arcs, of certain entities called nodes or vertices.

Description -

Bellman-ford algorithm works on relaxation technique. Basically in relaxation technique, we relaxes the edge. Relaxing an edge means checking to see if the path to the node, the edge is pointing to can’t be shortened, and if so, use it.

Bellman-Ford algorithm relaxes all the edge with V-1 times where V is the number of vertices in the graph. In each of these repetitions, we find the best path to the destination node which is passed through all the other nodes.

Step 3

Bellman – Ford Algorithm

Relaxation Technique

  • For each vertex v, we maintain an upper bound d[v] on the length of shortest path from source s to v
  • d[v] initialized to infinity
  • Relaxing an edge (u, v)
    • can we shorten the path to v by going through u?
    • If d[v] > d[u] + w(u,v), d[v] = d[u] + w(u,v) // Check whether the upper bound of d[v] is greater than the sum of upper bound d[u] and the weight of u to v
    • This can be done in O(1) time.

Algorithm

  • Bellman-Ford (G, w, s)
    • Initialize-Single-Source(G,s)
  • for (i=1 to V-1)
    • for each edge (u,v) in E
      • relax(u,v);
  • for each edge (u,v) in E
    • if d[v] > d[u] + w(u,v)
      • return NEGATIVE WEIGHT CYCLE

G = Graph, w = weight, s = source, V = no. of vertices, E = set or edges, u = initial point of edge, v = endpoint of edge.

Performance

Slower but flexible than Dijkstra’s algorithm.
Time complexity O(V.E).

 

 

Step 4

Bellman – Ford in PHP

</p>
<p>/*{source, destination, distance}*/</p>
<p>$edges =    array(</p>
<p>           array(0,1,5),</p>
<p>           array(0,2,8),</p>
<p>           array(0,3,-4),</p>
<p>           array(1,0,-2),</p>
<p>           array(2,1,-3),</p>
<p>           array(2,3,9),</p>
<p>           array(3,1,7),</p>
<p>           array(3,4,2),</p>
<p>           array(4,0,6),</p>
<p>           array(4,2,7),</p>
<p>       );</p>
<p>BELLMAN_FORD($edges,10,5,4);</p>
<p>function BELLMAN_FORD($edges, $edgecount, $nodecount, $source) {</p>
<p>    // Initialize distances</p>
<p>    $distances = array();</p>
<p>    // This is the INITIALIZE-SINGLE-SOURCE function.</p>
<p>    for($i =0; $i &lt; $nodecount;++$i)</p>
<p>        $distances[$i]= INF;// All distances should be set to INFINITY</p>
<p>    $distances[$source]=0;// The source distance should be set to 0.</p>
<p>    // Do what we are suppose to do, This is the BELLMAN-FORD function</p>
<p>     for($i =0; $i &lt; $nodecount;++$i) {</p>
<p>         $somethingChanged =false;// If nothing has changed after one pass, it will not change after two.</p>
<p>         for($j =0; $j &lt; $edgecount;++$j) {</p>
<p>             if($distances[$edges[$j][0]]!= INF) { // Check so we are not doing something stupid</p>
<p>                 $newDist = $distances[$edges[$j][0]]+ $edges[$j][2];// Just create a temporary variable containing the calculated distance</p>
<p>                 if($newDist &lt; $distances[$edges[$j][1]]) { // If the new distance is shorter than the old one, we've found a new shortest path </p>
<p>                     $distances[$edges[$j][1]]= $newDist;</p>
<p>                     $somethingChanged =true;// SOMETHING CHANGED, YEY!</p>
<p>                }</p>
<p>            }</p>
<p>        }</p>
<p>       // If $somethingChanged == FALSE, then nothing has changed and we can go on with the next step.</p>
<p>       if(!$somethingChanged)break;</p>
<p>    }</p>
<p>   // Check the graph for negative weight cycles</p>
<p>   for($i =0; $i &lt; $edgecount;++$i) {</p>
<p>        if($distances[$edges[$i][1]]&gt; $distances[$edges[$i][0]]+ $edges[$i][2]){</p>
<p>            echo &quot;Negative edge weight cycle detected!&quot;;</p>
<p>            return;</p>
<p>        }</p>
<p>    }</p>
<p>   // Print out the shortest distance</p>
<p>    for($i =0; $i &lt; $nodecount;++$i) {</p>
<p>        echo &quot;Shortest distance between nodes &quot;. $source .&quot; and &quot;. $i .&quot; is &quot;. $distances[$i]. &quot;&quot;;</p>
<p>    }</p>
<p>   return;</p>
<p>}</p>
<p>

Step 5

Output


Shortest distance between nodes 4 and 0 is 2
Shortest distance between nodes 4 and 1 is 4
Shortest distance between nodes 4 and 2 is 7
Shortest distance between nodes 4 and 3 is -2
Shortest distance between nodes 4 and 4 is 0
Udemy Generic 728x90

Spread the word. Share this post!

  • Vikas

    good
    thanks