We can easily find the shortest path using the Floyd-Warshall algorithm, but we do not get the actual path to go from node X to Y. This is because the Floyd-Warshall algorithm does the calculation for the distance or cost and does not store the actual path for the minimum cost. For example, using Google Maps, we can always find a route to our destination from any given location. Google Maps can show us the best route as regards the distance, time of travel, or other factors. This is a perfect example of single source shortest path algorithm usage. There are many algorithms to find the solution for a single source shortest path problem; however, Dijkstra's shortest path algorithm is the most popular one. There are many ways to implement Dijkstra's algorithm, such as using Fibonacci heaps, min-heaps, priority queues, and so on. Each implementation has its own advantage regarding the performance and improvement of Dijkstra's solution. Let's go through the pseudocode for the algorithm:

   function Dijkstra(Graph, source):

      create vertex set Q
      for each vertex v in Graph:   
          dist[v] := INFINITY
          prev[v] := UNDEFINED          
          add v to Q         

      dist[source] := 0           

      while Q is not empty:
          u := vertex in Q with min dist[u]
          remove u from Q

          for each neighbor v of u:
              alt := dist[u] + length(u, v)
              if alt < dist[v]:   
                  dist[v] := alt
                  prev[v] := u

      return dist[], prev[]

Now, we will implement the algorithm using a priority queue. First, let's choose a graph to implement the algorithm. We can select the following undirected weighted graph. It has six nodes with many connections between the nodes and vertices. First, we need to represent the following graph in an adjacency matrix:

As we can see from the preceding diagram, our vertices are labeled with the letters A to F, so we will use the vertex name as the key in a PHP associative array:

$graph = [
    'A' => ['B' => 3, 'C' => 5, 'D' => 9],
    'B' => ['A' => 3, 'C' => 3, 'D' => 4, 'E' => 7],
    'C' => ['A' => 5, 'B' => 3, 'D' => 2, 'E' => 6, 'F' => 3],
    'D' => ['A' => 9, 'B' => 4, 'C' => 2, 'E' => 2, 'F' => 2],
    'E' => ['B' => 7, 'C' => 6, 'D' => 2, 'F' => 5],
    'F' => ['C' => 3, 'D' => 2, 'E' => 5],
];

Now, we will implement Dijkstra's algorithm using a priority queue. We will find a path from the source vertex to the target vertex using the adjacency matrix we created for the last diagram. Our Dijkstra's algorithm will return an array with the minimum distance between two nodes and the followed path. We will return the path as a stack so that we can get the actual path in the reverse order. Here is the implementation:

function Dijkstra(array $graph, string $source,string $target):array{ 
    $dist = []; 
    $pred = []; 
    $Queue = new SplPriorityQueue(); 

    foreach ($graph as $v => $adj) { 
      $dist[$v] = PHP_INT_MAX; 
      $pred[$v] = null; 
      $Queue->insert($v, min($adj)); 
    } 

    $dist[$source] = 0; 

    while (!$Queue->isEmpty()) { 
      $u = $Queue->extract(); 
      if (!empty($graph[$u])) { 
          foreach ($graph[$u] as $v => $cost) { 
           if ($dist[$u] + $cost < $dist[$v]) { 
            $dist[$v] = $dist[$u] + $cost; 
            $pred[$v] = $u; 
        } 
          } 
      } 
    } 

    $S = new SplStack();
    $u = $target; 
    $distance = 0;

    while (isset($pred[$u]) && $pred[$u]) {
      $S->push($u);
      $distance += $graph[$u][$pred[$u]];
      $u = $pred[$u]; 
    } 

    if ($S->isEmpty()) { 
      return ["distance" => 0, "path" => $S]; 
    } else {
      $S->push($source);
      return ["distance" => $distance, "path" => $S]; 
    }
}

As we can see from the preceding implementation, first, we created two arrays to store the distance and predecessors, along with the priority queue. Then, we set each vertex as the maximum integer (PHP_INT_MAX) value of PHP (INFINITY in the pseudocode) and the predecessor as NULL. We also took the minimum value of all adjacent nodes and stored them in the queue. After the loop, we set the source node distance as 0. Then we checked each node in the queue and checked the nearest neighbors to find a minimum path. If a path is found using if ($dist[$u] + $cost < $dist[$v]), we assign it to the vertex.

We then created a stack named $s to store the path. We started from our target vertex and visited adjacent vertices to reach our source vertex. As we moved through the adjacent vertices, we also calculated the distance we covered by visiting those vertices. Since our function is returning both the distance and the path, we constructed an array to return both the distance and path for the given graph, source, and target. If no path exists, we return 0 as the distance and an empty stack for the output. Now, we will write a few lines of code to use the graph $graph and the function Dijkstra to check our implementation:

$source = "A"; 
$target = "F"; 

$result = Dijkstra($graph, $source, $target); 
extract($result); 

echo "Distance from $source to $target is $distance 
"; 
echo "Path to follow : "; 

while (!$path->isEmpty()) { 
    echo $path->pop() . "	"; 
} 

If we run this code, it will have the following output in our command line:

Distance from A to F is 8
Path to follow : A      C       F

The output looks exactly right, as we can see from the graph that the shortest path from A to F is through C and the shortest distance is 5 + 3 = 8.

Dijkstra's algorithm has a running complexity of O (V2). Since we are using the minimum priority queue, the runtime complexity is O (E + V log V).