Comment optimiser le code Dijkstra en PHP?

Question

Je précise cette question pour le code source PHP, où j'ai un code source pour Dijkstra écrit en PHP, quand j'applique cet algorithme sur Graph composé de baout 7000 nœuds, le processus devient extrêmement lent, et consomme un énorme espace de mémoire environ 1 GigaByte!

Je sais qu'il y a d'autres questions sur la façon d'optimiser Dijkstra .. Mais je veux savoir si j'ai implémenté l'algorithme Dijkstra en C comme extension PHP, est-ce que cela résout le problème? Y a-t-il d'autres suggestions?!

EDIT

code source pour l'algorithme Dijkstra ..

<?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 est un langage interprété comme n'est pas aussi efficace que java, C ou autres langages compilés. L'exécuter comme une extension serait beaucoup plus rapide.