php - Dijkstra algorithm optimization/caching

Question

I have the following Dijkstra algorithm with 3 input variables (start, stop and time). It takes about 0.5-1s to complete. My hosting provider says it's using too much resources and I should implement some caching mechanism. My question is, how?

Because I have 3 variables, if only one of them changes - the whole result is different (because I have some additional statements with time, nevermind). So how to implement some caching mechanism or do some optimisation?

I have 1700 nodes.

<?php require_once("../includes/db_connection.php"); ?>
<?php require("../includes/functions.php"); ?>
<?php require("../includes/global_variables.php"); ?>
<?php
    // Function to put "maxValues" into time (in my case 10 000 because I know it can't take longer than that from source to end node)
    function array_push_key(&$array, $key, $value) {
        $array[$key] = $value;
    }

    // Start the counter
    $timeM = microtime(); $timeM = explode(' ', $timeM); $timeM = $timeM[1] + $timeM[0]; $start = $timeM;

    // Get provided values
    $startStop = $_GET["start"];
    $endStop = $_GET["end"];
    $startTime = $_GET["time"];

    // Initialize arrays
    $time = array();
    $previousNode = array();
    $allStops = array();

    // [5] = 119 --> You can get to stop no. 5 by line no. 119
    // line to source node is 0
    $lineToThisStop = array();
    $lineToThisStop[$startStop] = 0;

    // Populate arrays
    $result=mysql_query("SELECT stop_id FROM db_stops", $connection);
    potvrdi_unos($result);
    $counter = 0;
    while($rows = mysql_fetch_array($result)){
        array_push_key($time, $rows["stop_id"], 10000);
        array_push($allStops, $rows["stop_id"]);
        // Locate startStop in the allStops array to unset it few lines later
        if ($rows["id"] == $startStop) {
            $poz = $brojac;
        }
        $counter++;
    }

    // Set starting time to starting stop
    $time[$startStop] = $startTime;
    // Set it activeNode
    $activeNode = $startStop;

    // Unset it in allStops array (so it doens't have to be checked later)
    unset($allStops[$poz]);
    $allStops = array_values($allStops);

    // I can put "while (true)" because all nodes are connected in "one piece", there is NO UNCONNECTED nodes
    while (true) {       
        $result=mysql_query("SELECT route_id, next_stop FROM db_stop_times WHERE stop_id = $activeNode", $connection);
        potvrdi_unos($result);

        while($rows = mysql_fetch_array($result)) {         
            // Draw paths from active node to all other (connected) stops
            $nextStopArray = $rows["next_stop"];

            // nextStopArray is something like "0,34,123,3123,213" - those are all stops from current, active node/stop
            $nextStopArray = explode(",", $nextStopArray);

            // sometimes it's just "4" to convert it into array
            if (!is_array($nextStopArray)) {
                $nextStopArray[0] = $nextStopArray;
            }

            for ($p = 0; $p < sizeof($nextStopArray); $p++) {
                $nextStop = $nextStopArray[$p];

                $walkToTheStop = false;

                // Few checks                   
                if ($p == 0) {
                    if ($nextStop != 0) {
                        $pathDuration = 2;                          

                        if ($lineToThisStop[$activeNode] != $rows["route_id"]) {
                            $pathDuration = $pathDuration * 2;
                        }
                    }
                } else {
                    $walkToTheStop = true;

                    $pathDuration = 1;                          
                }

                // If that's shortest path from ActiveNode to nextStop insert it into it's time array (time to get to that stop)
                if (($pathDuration + $time[$activeNode]) < $time[$nextStop]) {
                    $time[$nextStop] = $pathDuration + $time[$activeNode];

                    array_push_key($previousNode, $nextStop, $activeNode);

                    // Some aditional records (5000 means "you must walk to that stop")
                    if ($walkToTheStop) {
                        $lineToThisStop[$nextStop] = 5000;
                    } else {
                        $lineToThisStop[$nextStop] = $rows["route_id"];
                    }
                }
            }           
        }

        // Tra?i slijede?u stanicu (vrh) s najmanjom vrijednosti        
        $lowestValue = 10000 + 1;
        for ($j = 0; $j < sizeof($allStops); $j++) {
            if ($time[$allStops[$j]] < $lowestValue) {
                $lowestValue = $time[$allStops[$j]];                        
                $activeNode = $allStops[$j];

                // Record it's position so I can unset it later
                $activeNodePosition = $j;
            }
        }

        // Unset the active node from the array - so loop before will be shorter every time for one node/stop
        unset($allStops[$activeNodePosition]);
        $allStops = array_values($allStops);

        // If you get to the end stop, feel free to break out of the loop
        if ($activeNode == $endStop) {
            break;
        }
    }

    // How long did it take?
    $timeM = microtime(); $timeM = explode(' ', $timeM); $timeM = $timeM[1] + $timeM[0]; $finish = $timeM;

    $total_time = round(($finish - $start), 4);
    echo 'Total time '.$total_time.' seconds.'."<br />";
?>

<?php require_once("../includes/close_connection.php"); ?>

Answer 1

Micro-optimisations, but don't do:

for ($p = 0; $p < sizeof($nextStopArray); $p++) { 
   ...
}

calculate the sizeof($nextStopArray) before the loop, otherwise you're doing the count every iteration (and this value isn't being changed)

$nextStopArraySize = sizeof($nextStopArray);
for ($p = 0; $p < $nextStopArraySize; ++$p) { 
   ...
}

There's a couple of places where this should be changed.

And if you're iterating several thousand times, ++$p is faster than $p++

But profile the function... find out which parts are taking the longest to execute, and look to optimise those.

EDIT

Get rid of array_push_key as a function, simply execute it inline... it's costing you an unnecessary function call otherwise

Build an array of all nodes from your database outside of the while(true) loop... retrieve all the data in a single SQL query and build a lookup array.

Replacing

for ($p = 0; $p < sizeof($nextStopArray); $p++) { 

with

$nextStopArraySize = sizeof($nextStopArray);
$p = -1
while (++$p < $nextStopArraySize) { 
   ...
}

may also prove faster still (just check that the logic does loop through the correct number of times).