A common scenario for a pizza-delivery company is to deliver the pizza as quickly as possible. Graph algorithms can help us in such situations. The Floyd-Warshall algorithm is a very common algorithm that is used to find the shortest path from u to v using all pairs of vertices (u, v). The shortest path indicates the shortest possible distance between two nodes that are interconnected. The graph for calculating the shortest path has to be a weighted graph. In some cases, the weight can be negative as well. The algorithm is very simple and one of the easiest to implement. It is shown here:

for i:= 1 to n do 
  for j:= 1 to n do 
     dis[i][j] = w[i][j] 

for k:= 1 to n do 
   for i:= 1 to n do 
      for j:= 1 to n do 
         sum := dis[i][k] + dis[k][j] 
         if (sum < dis[i][j]) 
              dis[i][j] := sum 

First, we copied each of our weights to a cost or distance matrix. Then, we ran through each vertex and figured out the cost or distance of visiting from vertex i to vertex j through vertex k. If the distance or cost is less than a direct path between vertex i and vertex j, we choose the path i to k to j instead of the direct path of i to j. Let's consider the following diagram:

Here, we can see an undirected graph with weights on each edge. Now, if we look for the shortest path from A to E, then we have the following options:

• A to E via B has a distance of 20
• A to E via D has a distance of 25
• A to E via D and B has a distance of 20
• A to E via B and D has a distance of 35

So, we can see that the lowest distance is 20. Now, let's implement this programmatically with numeric representations of the vertices. We will use 0, 1, 2, 3, and 4 instead of A, B, C, D, and E, respectively. Now, let's represent the earlier graph in an adjacency matrix format:

$totalVertices = 5; 
$graph = []; 
for ($i = 0; $i < $totalVertices; $i++) { 
    for ($j = 0; $j < $totalVertices; $j++) { 
      $graph[$i][$j] = $i == $j ? 0 : PHP_INT_MAX; 
    }
}

Here, we took a difference approach and initialized all the edges to the maximum value of the PHP integer. The reason for doing this is to ensure that a value of 0 for non-edges does not impact the algorithm logic, as we are searching for the minimum value. Now, we need to add the weights to the graph as shown in the earlier diagram:

$graph[0][1] = $graph[1][0] = 10;
$graph[2][1] = $graph[1][2] = 5;
$graph[0][3] = $graph[3][0] = 5;
$graph[3][1] = $graph[1][3] = 5;
$graph[4][1] = $graph[1][4] = 10;
$graph[3][4] = $graph[4][3] = 20;

Since this is an undirected graph, we assign both edges the same value. If it were a directed graph, we could have made only one entry for each weight. Now, it is time to implement the Floyd-Warshall algorithm to find the shortest paths for any given pair of nodes. Here is our implementation of this function:

function floydWarshall(array $graph): array {
    $dist = [];
    $dist = $graph;
    $size = count($dist);

    for ($k = 0; $k < $size; $k++)
      for ($i = 0; $i < $size; $i++)
          for ($j = 0; $j < $size; $j++)
        $dist[$i][$j] = min($dist[$i][$j],
    $dist[$i][$k] + $dist[$k][$j]);

    return $dist;
} 

As we mentioned earlier, the implementation is really simple. We have three inner loops to calculate the minimum distance, and we also return the distance array at the end of the function. Now, let's call this function and check whether our expected results match:

$distance = floydWarshall($graph); 

echo "Shortest distance between A to E is:" . $distance[0][4] . "
"; 
echo "Shortest distance between D to C is:" . $distance[3][2] . "
"; 

Here is the output of the code:

Shortest distance between A to E is:20
Shortest distance between D to C is:10

If we check our previous graph, we can see that the shortest distance between D and C is actually 10, and the path is D → B → C (5+5), which is the shortest distance out of all the possible routes (D → A → B → C (20), or D → E → B → C (35)).

The complexity for the Floyd-Warshall algorithm is O (V3), where V is the number of vertices in the graph. Now we will explore another algorithm that is famous for finding the single source shortest path.