PHPでDijkstraコードを最適化するには？

Question

私はグラフ上でこのアルゴリズムはbaout 7000個のノードで構成されて適用されたときに、私は、私はPHPで書かれたダイクストラのソースコードを持っているPHPのソースコードについては、この質問を指定し、プロセスがめちゃめちゃ遅くになって、およびメモリの巨大なスペースを消費しています約1ギガバイト！

私はダイクストラを最適化する方法についての他の質問がある知っている...しかし、私はそれが問題を解決しない、PHPの拡張としてCでダイクストラアルゴリズムを実装しているかどうかを知りたいですか？他の提案はありますか？

EDITダイクストラアルゴリズムの

ソースコード..

<?php 
//ini_set('memory_limit', '1M'); //Raise to 512 MB 
//ini_set('max_execution_time', '60'); //Raise to 512 MB 
class Dijkstra { 

    var $visited = array(); 
    var $distance = array(); 
    var $previousNode = array(); 
    var $startnode =null; 
    var $map = array(); 
    var $infiniteDistance = 0; 
    var $numberOfNodes = 0; 
    var $bestPath = 0; 
    var $matrixWidth = 0; 

    function Dijkstra(&$ourMap, $infiniteDistance) { 
     $this -> infiniteDistance = $infiniteDistance; 
     $this -> map = &$ourMap; 
     $this -> numberOfNodes = count($ourMap); 
     $this -> bestPath = 0; 
    } 

    function findShortestPath($start,$to) { 
     $this -> startnode = $start; 
     for ($i=0;$i<$this -> numberOfNodes;$i++) { 
      if ($i == $this -> startnode) { 
       $this -> visited[$i] = true; 
       $this -> distance[$i] = 0; 
      } else { 
       $this -> visited[$i] = false; 
       $this -> distance[$i] = isset($this -> map[$this -> startnode][$i]) 
        ? $this -> map[$this -> startnode][$i] 
        : $this -> infiniteDistance; 
      } 
      $this -> previousNode[$i] = $this -> startnode; 
     } 

     $maxTries = $this -> numberOfNodes; 
     $tries = 0; 
     while (in_array(false,$this -> visited,true) && $tries <= $maxTries) {    
      $this -> bestPath = $this->findBestPath($this->distance,array_keys($this -> visited,false,true)); 
      if($to !== null && $this -> bestPath === $to) { 
       break; 
      } 
      $this -> updateDistanceAndPrevious($this -> bestPath);    
      $this -> visited[$this -> bestPath] = true; 
      $tries++; 
     } 
    } 

    function findBestPath($ourDistance, $ourNodesLeft) { 
     $bestPath = $this -> infiniteDistance; 
     $bestNode = 0; 
     for ($i = 0,$m=count($ourNodesLeft); $i < $m; $i++) { 
      if($ourDistance[$ourNodesLeft[$i]] < $bestPath) { 
       $bestPath = $ourDistance[$ourNodesLeft[$i]]; 
       $bestNode = $ourNodesLeft[$i]; 
      } 
     } 
     return $bestNode; 
    } 

    function updateDistanceAndPrevious($obp) {   
     for ($i=0;$i<$this -> numberOfNodes;$i++) { 
      if( (isset($this->map[$obp][$i])) 
       && (!($this->map[$obp][$i] == $this->infiniteDistance) || ($this->map[$obp][$i] == 0))  
       && (($this->distance[$obp] + $this->map[$obp][$i]) < $this -> distance[$i]) 
      )  
      { 
        $this -> distance[$i] = $this -> distance[$obp] + $this -> map[$obp][$i]; 
        $this -> previousNode[$i] = $obp; 
      } 
     } 
    } 

    function printMap(&$map) { 
     $placeholder = ' %' . strlen($this -> infiniteDistance) .'d'; 
     $foo = ''; 
     for($i=0,$im=count($map);$i<$im;$i++) { 
      for ($k=0,$m=$im;$k<$m;$k++) { 
       $foo.= sprintf($placeholder, isset($map[$i][$k]) ? $map[$i][$k] : $this -> infiniteDistance); 
      } 
      $foo.= "\n"; 
     } 
     return $foo; 
    } 

    function getResults($to) { 
    if(trim($to)!="") 
    { 
     $ourShortestPath = array(); 
     $foo = ''; 
     for ($i = 0; $i < $this -> numberOfNodes; $i++) { 
      if($to !== null && $to !== $i) { 
       continue; 
      } 
      $ourShortestPath[$i] = array(); 
      $endNode = null; 
      $currNode = $i; 
      $ourShortestPath[$i][] = $i; 
      while ($endNode === null || $endNode != $this -> startnode) { 
       $ourShortestPath[$i][] = $this -> previousNode[$currNode]; 
       $endNode = $this -> previousNode[$currNode]; 
       $currNode = $this -> previousNode[$currNode]; 
      } 
      $ourShortestPath[$i] = array_reverse($ourShortestPath[$i]); 
      if ($to === null || $to === $i) { 
      if($this -> distance[$i] >= $this -> infiniteDistance) { 
       $foo .= sprintf("no route from %d to %d. \n",$this -> startnode,$i); 
      } else { 
       $foo .= sprintf(' - Distance = %d (km) <br> - Walking time ~ %d (hrs)<br> - Running time ~ %d (hrs)<br> - Driving time ~ %d (hrs)<br> Nodes [%d] : %s'."\n" , 
         $this -> distance[$i], round($this -> distance[$i]/5,2),$this -> distance[$i]/17.2,$this -> distance[$i]/50, 
         count($ourShortestPath[$i]), 
         implode('-',$ourShortestPath[$i])); 
      } 
       if ($to === $i) { 
        break; 
       } 
      } 
     } 
     } 
     else $foo=""; 
     return $foo; 
    } 
} // end class 
?> 

Answer 1

PHPは、Java、Cまたは他のコンパイル言語ほど効率的ではないと解釈言語です。拡張機能として実行する方がはるかに高速です。