A PHP implementation of the Dijkstra algorithm to find a good path to travel between two nodes

Dijkstra.php

<?php



function dijkstraRoute($matrix, $start, $stop) {

    $Q = array(); // this will be the array containing the estimated cost to each node
    $S = array(); //this set will have, for each key, the prevoious node and the cost to reach it
    foreach (array_keys($matrix) as $node) $Q[$node] = 99999; // assume this value as infinite
    $Q[$start] = 0;

    while(!empty($Q)) {

        $min = array_search(min($Q), $Q);
        if($min == $stop) break; // finished
        foreach ($matrix[$min] as $key => $val) {
            if(isset($Q[$key]) && $Q[$min] + $val < $Q[$key]) {
                $Q[$key] = $Q[$min] + $val;
                $S[$key] = array($min, $Q[$key]);
            }
        }
        unset($Q[$min]);

    }

    $path = array();
    $pos = $stop; 

    // starting from the last node, we add this key to the path array and redefine pos as the previous node for this key in the array of S
    while($pos != $start) { 
        $path[]= $pos;
        $pos = $S[$pos][0];
    }
    $path[]= $start;

    return array_reverse($path);


}




$nodes_matrix = array();

$nodes_matrix[1][2] = 1;
$nodes_matrix[1][3] = 6;
$nodes_matrix[1][4] = 7;
$nodes_matrix[2][1] = 1;
$nodes_matrix[2][3] = 8;
$nodes_matrix[2][4] = 2;
$nodes_matrix[3][1] = 6;
$nodes_matrix[3][2] = 8;
$nodes_matrix[3][4] = 2;
$nodes_matrix[4][1] = 7;
$nodes_matrix[4][2] = 2;
$nodes_matrix[4][3] = 2;


$start = 1;
$stop = 4;

echo implode('->', dijkstraRoute($nodes_matrix, $start, $stop));