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