php - 如何在 PHP 中优化 Dijkstra 代码？

Question

我为 PHP 源代码指定了这个问题，其中我有一个用 PHP 编写的 Dijkstra 源代码，当我在由 baout 7000 个节点组成的图上应用这个算法时，这个过程变得非常缓慢，并且消耗了巨大的空间内存约 1 GB!

我知道还有其他关于如何优化 Dijkstra 的问题。但是我想知道我是否已经在 C 中将 Dijkstra 算法作为 PHP 扩展实现，这是否解决了问题？还有其他建议吗？？!

编辑

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 是一种解释型语言，不如 java、C 或其他编译型语言高效。作为扩展运行它会快得多。