infiniteDistance = $infiniteDistance; $this -> map = &$ourMap; $this -> numberOfNodes = count($ourMap); $this -> bestPath = 0; $this -> city_array = $city_array; } function findShortestPath($start,$to) { $this -> startnode = $start; foreach ($this -> map as $key => $value) { $this -> visited[$key] = false; $this -> distance[$key] = isset($this -> map[$this -> startnode][$key]) ? $this -> map[$this -> startnode][$key]: $this -> infiniteDistance; $this -> previousNode[$key] = $this -> startnode; } $this -> visited[$this -> startnode] = true; $this -> distance[$this -> startnode] = 0; $this->current_node=$this -> startnode; $this->sorted_distance = $this->distance; unset($this->sorted_distance[$this -> startnode]); $maxTries = $this -> numberOfNodes; $tries = 0; while (in_array(false,$this -> visited,true) && $tries <= $maxTries) { $this -> bestPath = $this->findBestPath(); if($this -> bestPath == $to) break; $this -> updateDistanceAndPrevious($this -> bestPath); $this -> visited[$this -> bestPath] = true; $tries++; } } function findBestPath($ourNodesLeft=array()) { asort($this->sorted_distance); foreach ($this->sorted_distance as $key =>$value) break; unset($this->sorted_distance[$key]); return $key; } function updateDistanceAndPrevious($obp) { if (is_array($this -> city_array[$obp][neighbors])){ foreach ($this -> city_array[$obp][neighbors] as $key => $value) { if( (($this->distance[$obp] + $this->map[$obp][$value]) < $this -> distance[$value]) && (isset($this->map[$obp][$value])) ) { $this -> distance[$value] = $this -> distance[$obp] + $this -> map[$obp][$value]; $this -> sorted_distance[$value] = $this -> distance[$value]; $this -> previousNode[$value] = $obp; } } } } function getResults($to) { if ($to==0) return array(); $ourShortestPath = array(); $endNode = null; $currNode = $to; $ourShortestPath[] = $to; $i=0; while ($endNode === null || $endNode != $this -> startnode) { $ourShortestPath[] = $this -> previousNode[$currNode]; $endNode = $this -> previousNode[$currNode]; $currNode = $this -> previousNode[$currNode]; $i++; if ($i>=1000) return array();//exit when circle } $ourShortestPath = array_reverse($ourShortestPath); if($this -> distance[$to] >= $this -> infiniteDistance) return array(); return $ourShortestPath; } } ?> ЦКМ КПІ
Центр Культури та Мистецтв
вітає Вас
Наша історія