PatchFind\Algorithm\Dijkstra::calculateRoad()

Complexity

Conditions	8
Paths	8

Size

Total Lines	31
Code Lines	22

Duplication

Lines	0
Ratio	0 %

Importance

Changes	1
Bugs	0	Features	0

<?php
        public function calculateRoad($startX, $startY, $endX, $endY, $graph){
            $a = "(".$startX.",".$endX.")";
            $b = "(".$startY.",".$endY.")";
            
            $short = array(); 
            $query = array();
            foreach(array_keys($graph) as $v) $query[$v] = 99999;
            $query[$a] = 0;

            while(!empty($query)){
                $min = array_search(min($query), $query);
                if($min === $b) break;
                foreach($graph[$min] as $key => $v){
                    if(!empty($query[$key]) && $query[$min] + $v < $query[$key]){
                        $query[$key] = $query[$min] + $v;
                        $short[$key] = array($min, $query[$key]);
                    }
                }
                unset($query[$min]);
            }

            $path = array();
            $pos = $b;
            while($pos != $a){
                $path[] = $pos;
                $pos = $short[$pos][0];
            }
            $path[] = $a;
            $path = array_reverse($path);

            return $path;
        }
    }