Though Dijkstra's algorithm is the most popular and efficient one that is used to find the single source shortest path, there is one problem that it does not address. If the graph has a negative cycle, Dijkstra's algorithm cannot detect the negative cycle, and, thus, it does not work. A negative cycle is a cycle where the sum of all the edges in the cycle is negative. If a graph contains a negative cycle, then finding the shortest path will not be possible, so it is important that we address the issue while finding the shortest path. That is why we use the Bellman-Ford algorithm, even though it is slower compared to Dijkstra's algorithm. Here is the algorithm pseudocode for the Bellman-Ford algorithm for the shortest path:

function BellmanFord(list vertices, list edges, vertex source) 
  // This implementation takes a vertex source 
  // and fills distance array with shortest-path information 

  // Step 1: initialize graph 
  for each vertex v in vertices: 
    if v is source 
      distance[v] := 0 
    else 
      distance[v] := infinity 

  // Step 2: relax edges repeatedly 
  for i from 1 to size(vertices)-1: 
    for each edge (u, v) with weight w in edges: 
      if distance[u] + w < distance[v]: 
        distance[v] := distance[u] + w 

  // Step 3: check for negative-weight cycles 
    for each edge (u, v) with weight w in edges: 
        if distance[u] + w < distance[v]: 
      error "Graph contains a negative-weight cycle" 

We can see that the Bellman-Ford algorithm also considers the edge sand vertices in finding the shortest path between nodes. This is known as the relaxation process, which is also used in Dijkstra's algorithm. The relaxation process in graph algorithms refers to the updating of the cost of all vertices connected to a vertex V if those costs would be improved by including the path via V. In simple words, the relaxation process is trying to lower the cost of getting to a vertex using another vertex. Now, we will implement this algorithm for the same graph we used in Dijkstra's algorithm. The only difference is that here we will use numeric labels for our nodes and vertex here:

Now it is time to represent the graph in an adjacency matrix format. Here is the matrix in PHP:

$graph = [ 
    0 => [0, 3, 5, 9, 0, 0], 
    1 => [3, 0, 3, 4, 7, 0], 
    2 => [5, 3, 0, 2, 6, 3], 
    3 => [9, 4, 2, 0, 2, 2], 
    4 => [0, 7, 6, 2, 0, 5], 
    5 => [0, 0, 3, 2, 5, 0] 
]; 

Previously, we used a value of 0 to indicate that there was no edge between two vertices. If we do the same here, then taking a minimum between two edges where one represents 0 will always yield a 0 during the relaxation process, which actually means that there is no connection between two vertices. As a result, we have to choose a larger number to represent the non-existent edges. We can use the MAX_INT_VALUE constant of PHP to represent those edges so that those non-existent edges are not considered. This can be our new graph representation:

define("I", PHP_INT_MAX); 

$graph = [ 
    0 => [I, 3, 5, 9, I, I], 
    1 => [3, I, 3, 4, 7, I], 
    2 => [5, 3, I, 2, 6, 3], 
    3 => [9, 4, 2, I, 2, 2], 
    4 => [I, 7, 6, 2, I, 5], 
    5 => [I, I, 3, 2, 5, I] 
]; 

Now, let's write the implementation for the Bellman-Ford algorithm. We will use the same approach we defined in the pseudocode:

function bellmanFord(array $graph, int $source): array { 
    $dist = []; 
    $len = count($graph); 

    foreach ($graph as $v => $adj) { 
      $dist[$v] = PHP_INT_MAX; 
    } 

    $dist[$source] = 0; 

    for ($k = 0; $k < $len - 1; $k++) { 
      for ($i = 0; $i < $len; $i++) { 
          for ($j = 0; $j < $len; $j++) { 
            if ($dist[$i] > $dist[$j] + $graph[$j][$i]) { 
            $dist[$i] = $dist[$j] + $graph[$j][$i]; 
        } 
          } 
      } 
    } 

    for ($i = 0; $i < $len; $i++) { 
      for ($j = 0; $j < $len; $j++) { 
          if ($dist[$i] > $dist[$j] + $graph[$j][$i]) { 
           echo 'The graph contains a negative-weight cycle!'; 
           return []; 
          } 
      } 
        } 
    return $dist; 
} 

Unlike Dijkstra's algorithm, we are not tracking the predecessors. We are considering the distance during the relaxation process. Since we are using the maximum value for an integer in PHP, it automatically cancels outs the possibility of choosing a nonexistent edge with a value of 0 as the minimum path. The last part of the implementation detects any negative cycle in the given graph and returns an empty array in that case:

$source = 0; 
$distances = bellmanFord($graph, $source); 

foreach($distances as $target => $distance) { 
    echo "distance from $source to $target is $distance 
"; 
} 

This will have the following output, which shows the shortest path distance from our source node to other nodes:

distance from 0 to 0 is 0
distance from 0 to 1 is 3
distance from 0 to 2 is 5
distance from 0 to 3 is 7
distance from 0 to 4 is 9
distance from 0 to 5 is 8

The Bellman-Ford algorithm has the run-time complexity of O (V, E).