<?php 
define('I',100000); // define infinite distance 

/** 
 * class to Build Dijkstra model 
 * To build the class  
 * Use int to index all the points on the map 
 * @param int startPoint 
 * @param array routes[] = array($startPoint,$endPoint,$distance) 
 * @author Rick.purple 
 */ 

class Dijkstra{ 
    private $intStartPoint;  
    private $aRoutes = array(); // all possible routes between each two points (single direction)  
    private $aPoints = array(); // all the points on the map 
    private $aReds = array();    
    private $aBlues = array();  
    private $aDistances = array(); // the closest distance from start point to each points 
    private $aPathes = array(); // path from each points to its neibor on the best path to the start point 
    private $aFullPathes; // path from start point to each points 
     
    /** 
     * Build Dijkstra model, find best path and closest distance from start point to each point on the map  
     * @return null 
     * @param object $intStartPoint  
     * @param object $aRoutes 
     */ 
    public function __construct($intStartPoint,$aRoutes){ 
        $this->aRoutes = $aRoutes; 
        $this->intStartPoint = $intStartPoint; 
         
        foreach($aRoutes as $aRoute){ 
            if(!in_array($aRoute[0],$this->aPoints)){ 
                $this->aPoints[] = $aRoute[0]; 
            } 
            if(!in_array($aRoute[1],$this->aPoints)){ 
                $this->aPoints[] = $aRoute[1]; 
            }     
        }     
         
        $this->aReds = array($intStartPoint); 
        $this->aBlues = $this->array_remove($this->aPoints, $intStartPoint);     
         
        foreach($this->aBlues as $intPoint){ 
                $this->aDistances[$intPoint] = I; 
        } 
        $this->aDistances[$intStartPoint] = 0;     
         
        $this->findPath(); 
    } 

    /** 
     * function to get the best path 
     * @return pathes for each node on the map 
     */     
    public function getPath(){ 
        foreach($this->aPoints as $intPoint){ 
            $this->fillFullPath($intPoint,$intPoint); 
        } 
        return $this->aFullPathes; 
    } 
     
    /** 
     * function to get the closest distance      
     * @return  
     */ 
    public function getDistance(){ 
        return $this->aDistances; 
    }     

    /** 
     * Remove specified element from array 
     * @return array  
     * @param array $arr : array to be processing 
     * @param array $value : the element to be remove from the array 
     */     
    private function array_remove($arr,$value) { 
        return array_values(array_diff($arr,array($value))); 
    } 
     
    /** 
     * Dijkstra algorithm implementation 
     * @return null 
     */ 
    private function findPath(){ 
        while(!empty($this->aBlues)){ 
            $intShortest = I; 
            foreach($this->aReds as $intRed){ 
                # find possible rounte 
                foreach($this->aRoutes as $aRoute){ 
                    if($intRed == $aRoute[0]){ 
                        $aDis[$intRed][$aRoute[1]] = $aRoute[2]; 
                         
                        # rewrite distance 
                        $intDistance = $this->aDistances[$intRed] + $aRoute[2]; 
                        if($this->aDistances[$aRoute[1]] > $intDistance){ 
                            $this->aDistances[$aRoute[1]] = $intDistance; 
                            # change the path 
                            if($intRed==$this->intStartPoint ||$intRed==$aRoute[1]){} 
                            else{ 
                                $this->aPathes[$aRoute[1]] = $intRed; 
                            } 
                        } 
                         
                        # find the nearest    neighbor 
                        if(!in_array($aRoute[1],$this->aReds)&&$aRoute[2]<$intShortest){ 
                            $intShortest = $aRoute[2]; 
                            $intAddPoint = $aRoute[1]; 
                        }         
                    } 
                } 
            } 

            $this->aReds[] = $intAddPoint; 
            $this->aBlues = $this->array_remove($this->aBlues, $intAddPoint);     
        } 
    } 

    /** 
     * mid step function to find full path from start point to the end point. 
     * @return null 
     * @param int $intEndPoint 
     * @param int $intMidPoint 
     */         
    private function fillFullPath($intEndPoint,$intMidPoint){ 
        if(isset($this->aPathes[$intMidPoint])){ 
            $this->aFullPathes[$intEndPoint][] = $this->aPathes[$intMidPoint]; 
            $this->fillFullPath($intEndPoint,$this->aPathes[$intMidPoint]); 
        } 
        else{ 
            $this->aFullPathes[$intEndPoint][] = $this->intStartPoint; 
        }                     
    } 
} 

# Examples  
// single direction route path 
$aRoutes = array( 
    array(0,0,0), 
    array(0,1,10), 
    array(0,3,30), // use something like array(3,0,20) to define a two way map    
    array(0,4,100), 
    array(1,1,0), 
    array(1,2,50), 
    array(2,2,0), 
    array(2,4,10), 
    array(3,3,0), 
    array(3,2,20), 
    array(3,4,60), 
    array(4,4,0), 
); 
$oDijk = new Dijkstra(0,$aRoutes); // startPoint = 0 

print_r($oDijk->getPath()); 
print_r($oDijk->getDistance()); 

?>