Read 539 times | Created 2017-07-10 21:59:46 | Updated 2017-07-13 19:41:25 | | |

<?PHP
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 = null) {
        $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 = null) {
        $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('%d => %d = %d [%d]: (%s).'."n" ,
                        $this -> startnode,$i,$this -> distance[$i],
                        count($ourShortestPath[$i]),
                        implode('-',$ourShortestPath[$i]));
            }
            $foo .= str_repeat('-',20) . "n";
                if ($to === $i) {
                    break;
                }
            }
        }
        return $foo;
    }
} // end class
?>
 
<?php
 
// I is the infinite distance.
define('I',1000);
 
// Size of the matrix
$matrixWidth = 20;
 
// $points is an array in the following format: (router1,router2,distance-between-them)
$points = array(
    array(0,1,4),
    array(0,2,I),
    array(1,2,5),
    array(1,3,5),
    array(2,3,5),
    array(3,4,5),
    array(4,5,5),
    array(4,5,5),
    array(2,10,30),
    array(2,11,40),
    array(5,19,20),
    array(10,11,20),
    array(12,13,20),
);
 
$ourMap = array();
 
 
// Read in the points and push them into the map
 
for ($i=0,$m=count($points); $i<$m; $i++) {
    $x = $points[$i][0];
    $y = $points[$i][1];
    $c = $points[$i][2];
    $ourMap[$x][$y] = $c;
    $ourMap[$y][$x] = $c;
}
 
// ensure that the distance from a node to itself is always zero
// Purists may want to edit this bit out.
 
for ($i=0; $i < $matrixWidth; $i++) {
    for ($k=0; $k < $matrixWidth; $k++) {
        if ($i == $k) $ourMap[$i][$k] = 0;
    }
}
 
 
// initialize the algorithm class
$dijkstra = new Dijkstra($ourMap, I,$matrixWidth);
 
// $dijkstra->findShortestPath(0,13); to find only path from field 0 to field 13...
$dijkstra->findShortestPath(0);
 
// Display the results
 
echo '<pre>';
echo "the map looks like:nn";
echo $dijkstra -> printMap($ourMap);
echo "nnthe shortest paths from point 0:n";
echo $dijkstra -> getResults();
echo '</pre>';
 
?>