php - Dijkstra algorithm optimization/caching -

i have following dijkstra algorithm 3 input variables (start, stop , time). takes 0.5-1s complete. hosting provider says it's using resources , should implement caching mechanism. question is, how?

because have 3 variables, if 1 of them changes - whole result different (because have additional statements time, nevermind). how implement caching mechanism or 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 put "maxvalues" time (in case 10 000 because know can't take longer source end node)     function array_push_key(&$array, $key, $value) {         $array[$key] = $value;     }      // start counter     $timem = microtime(); $timem = explode(' ', $timem); $timem = $timem[1] + $timem[0]; $start = $timem;      // provided values     $startstop = $_get["start"];     $endstop = $_get["end"];     $starttime = $_get["time"];      // initialize arrays     $time = array();     $previousnode = array();     $allstops = array();      // [5] = 119 --> can stop no. 5 line no. 119     // line source node 0     $linetothisstop = array();     $linetothisstop[$startstop] = 0;      // populate arrays     $result=mysql_query("select stop_id 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 allstops array unset few lines later         if ($rows["id"] == $startstop) {             $poz = $brojac;         }         $counter++;     }      // set starting time starting stop     $time[$startstop] = $starttime;     // set activenode     $activenode = $startstop;      // unset in allstops array (so doens't have checked later)     unset($allstops[$poz]);     $allstops = array_values($allstops);      // can put "while (true)" because nodes connected in "one piece", there no unconnected nodes     while (true) {                $result=mysql_query("select route_id, next_stop db_stop_times stop_id = $activenode", $connection);         potvrdi_unos($result);          while($rows = mysql_fetch_array($result)) {                      // draw paths active node other (connected) stops             $nextstoparray = $rows["next_stop"];              // nextstoparray "0,34,123,3123,213" - stops current, active node/stop             $nextstoparray = explode(",", $nextstoparray);              // it's "4" convert array             if (!is_array($nextstoparray)) {                 $nextstoparray[0] = $nextstoparray;             }              ($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 activenode nextstop insert it's time array (time stop)                 if (($pathduration + $time[$activenode]) < $time[$nextstop]) {                     $time[$nextstop] = $pathduration + $time[$activenode];                      array_push_key($previousnode, $nextstop, $activenode);                      // aditional records (5000 means "you must walk stop")                     if ($walktothestop) {                         $linetothisstop[$nextstop] = 5000;                     } else {                         $linetothisstop[$nextstop] = $rows["route_id"];                     }                 }             }                    }          // traži slijedeću stanicu (vrh) s najmanjom vrijednosti                 $lowestvalue = 10000 + 1;         ($j = 0; $j < sizeof($allstops); $j++) {             if ($time[$allstops[$j]] < $lowestvalue) {                 $lowestvalue = $time[$allstops[$j]];                                         $activenode = $allstops[$j];                  // record it's position can unset later                 $activenodeposition = $j;             }         }          // unset active node array - loop before shorter every time 1 node/stop         unset($allstops[$activenodeposition]);         $allstops = array_values($allstops);          // if end stop, feel free break out of loop         if ($activenode == $endstop) {             break;         }     }      // how long did 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"); ?> 

micro-optimisations, don't do:

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

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

$nextstoparraysize = sizeof($nextstoparray); ($p = 0; $p < $nextstoparraysize; ++$p) {     ... } 

there's couple of places should changed.

and if you're iterating several thousand times, ++$p faster $p++

but profile function... find out parts taking longest execute, , optimise those.

edit

get rid of array_push_key function, execute inline... it's costing unnecessary function call otherwise

build array of nodes database outside of while(true) loop... retrieve data in single sql query , build lookup array.

replacing

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

with

$nextstoparraysize = sizeof($nextstoparray); $p = -1 while (++$p < $nextstoparraysize) {     ... } 

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