Last active
August 29, 2016 21:48
-
-
Save kulikov/2267138 to your computer and use it in GitHub Desktop.
дейкстра
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<?php | |
/** | |
* Нахождение кратчайшего пути между двумя произвольными вершинами в графе | |
* http://ru.wikipedia.org/wiki/Алгоритм_Дейкстры | |
*/ | |
class Dijkstra | |
{ | |
private $_graph = array(); | |
private $_nodes = array(); | |
private $_result = array(); | |
public function __construct($graph) | |
{ | |
$this->_graph = $graph; | |
} | |
public function calc($from, $to) | |
{ | |
// сбрасываем предыдущие результаты | |
$this->_nodes = $this->_result = array(); | |
foreach ($this->_graph as $path) { | |
$this->_nodes[$path[0]][$path[1]] = $this->_nodes[$path[1]][$path[0]] = $path[2]; | |
} | |
$this->_nodes[$from][$from] = 0; // чтобы лишний раз не считать | |
$currentWeight = 0; | |
$src = $from; | |
while ($this->_nodes) { | |
$node = $this->_nodes[$src]; // берем ноду | |
asort($node); // сортируем по весу | |
// пробегаемся по всем ее соседям и пересчитываем их вес | |
foreach ($node as $dest => $weight) { | |
if (!isset($this->_result[$dest]) || ($currentWeight + $weight) < $this->_result[$dest]) { | |
$this->_result[$dest] = $currentWeight + $weight; // находим наименьшее растояние до этой точки | |
} | |
} | |
unset($this->_nodes[$src]); // отмечаем как посчитанную | |
// переходим к следующей вершине | |
$node = array_intersect_key($node, $this->_nodes); // исключаем уже посещенные точки | |
$src = $node ? key($node) : key($this->_nodes); // если дальше нет свободной ноды то берем просто следующую непосчитанную из графа (???) | |
$currentWeight = isset($this->_result[$src]) ? $this->_result[$src] : 0; // растояние до этой ноды от старта | |
} | |
return $this->_result[$to]; | |
} | |
} | |
$graph1 = array( | |
array(1, 2, 7), | |
array(1, 3, 9), | |
array(1, 6, 14), | |
array(2, 3, 10), | |
array(2, 4, 15), | |
array(3, 4, 11), | |
array(3, 6, 2), | |
array(4, 5, 6), | |
array(5, 6, 9), | |
); | |
$graph2 = array( | |
array("Barcelona", "Narbonne", 250), | |
array("Narbonne", "Marseille", 260), | |
array("Narbonne", "Toulouse", 150), | |
array("Narbonne", "Geneve", 550), | |
array("Marseille", "Geneve", 470), | |
array("Toulouse", "Paris", 680), | |
array("Toulouse", "Geneve", 700), | |
array("Geneve", "Paris", 540), | |
array("Geneve", "Lausanne", 64), | |
array("Lausanne", "Paris", 536), | |
); | |
$dijkstra1 = new Dijkstra($graph1); | |
print $dijkstra1->calc(1, 5); // => 20 | |
$dijkstra2 = new Dijkstra($graph2); | |
print $dijkstra2->calc('Barcelona', 'Lausanne'); // => 864 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment