PHP: Алгоритм Дейкстры - поиск кратчайшего пути
Поиск самого выгодного (быстрого, дешёвого: зависит от выбранного веса) пути с помощью алгоритма на взвешенных графах. «Алгоритм Дейкстры» находит кратчайшие пути от одной из вершин графа до всех остальных.
Для примера найдём самый быстрый путь из точки A в точку D.
Каждая точка - это узел (node). Линия, соединяющая точки - это ребро. Между точками указан вес - время для перехода от точки к точке.
$target = 'D'; // Граф для моделирования связи между узлами (определения соседей) $graph = [ 'A' => [ // из А можно попасть в точки B и C 'B' => 9, 'C' => 3, ], 'C' => [ 'B' => 4, 'D' => 7, ], 'B' => [ 'D' => 1, ], 'D' => [] ]; // Хранит время, которое потребуется для перехода к узлу от начального узла A $times = [ 'B' => 9, // Из точки А в точку B можно добраться за 9 минут 'C' => 3, 'D' => INF // Неизвестно (равно бесконечности) время, которое потребуется, чтобы добраться из точки А в точку D ]; // Хранит родителя - узел из которого пришли $parents = [ 'B' => 'A', // В точку B пришли из точки А 'C' => 'A', 'D' => null, // Неизвестно как попасть в точку D ];
Во процессе работы алгоритма будут обновляться массивы times и parents. В каждой итерации алгоритм ищет узел, до которого можно добраться за минимальное время и обновляет общее время.
class dijkstra { private $checked; public function __construct() { $this->checked = []; } function findFastestNode( $times ) { $minTime = INF; $fastestNode = null; foreach( $times as $n => $time ) { if( $time < $minTime AND !in_array( $n, $this->checked ) ) { $minTime = $time; $fastestNode = $n; } } return $fastestNode; } public function find( $graph, $times, $parents, $target ) { $node = $this->findFastestNode( $times ); while( $node != null ) { $time = $times[ $node ]; $neighbors = $graph[ $node ]; foreach( $neighbors as $neighborNode => $neighborTime ) { $newTime = $time + $neighborTime; if( $times[ $neighborNode ] > $newTime ) { $times[ $neighborNode ] = $newTime; $parents[ $neighborNode ] = $node; } } array_push( $this->checked, $node ); $node = $this->findFastestNode( $times ); } echo '<pre>', var_dump( $times ) ,'</pre>'; // > array(3) { // > ["B"]=> // > int(7) // > ["C"]=> // > int(3) // > ["D"]=> // > int(8) // > } // В результате: // минимальное время из точки A в точку B равно 7 // минимальное время из точки A в точку С равно 3 // минимальное время из точки A в точку D равно 8 echo '<pre>', var_dump( $parents ) ,'</pre>'; // > array(3) { // > ["B"]=> // > string(1) "C" // > ["C"]=> // > string(1) "A" // > ["D"]=> // > string(1) "B" // > } // В результате: // в точку D пришли из точки B // в точку B пришли из точки C // в точку C пришли из точки A // Маршрут А -> С -> B -> D за минимальное время = 8 return $times[ $target ]; } } $alg = new dijkstra(); $minTime = $alg->find( $graph, $times, $parents, $target ); echo 'Минимальное время из А в '. $target .' составляет: '. $minTime ; // > Минимальное время из А в D составляет: 8
Комментарии