Алгоритм Дейкстры

	class MyDijkstra
	{
	    // в этом свойстве хранится сам граф
	    protected $graph;
	    // массив с метками для вершин. Ячейка L в видео.
	    protected $l;
	    // массив с вершинами, в которых хранятся значения предков
	    // согласно тому как обходятся вершины графа. Ячейка Q в видео.
	    protected $q;
	    // массив посещённых вершин. Сюда мы добавляем метки, у которых
	    // значения уже имеют постоянные метки и изменяться не будут.
	    protected $visited;
	    // эта переменная вернёт значения ячейки Q, то есть в
	    // эту переменную сохранится конечное значение переменной $q
	    public $result_q;

	    public function __construct($graph, $source)
	    {
	        $this->graph = $graph;
	        $this->l = [];
	        $this->q = [];
	        $this->visited = [];
	        // для начала всем элементам массив $l для каждой
	        // вершины в качестве веса устанавливаем бесконечность,
	        // а массив $q остаётся пустой
	        foreach ($this->graph as $key => $value){
	            $this->l[$key] = INF;
	            $this->q[$key] = NULL;
	        }
	        // а вершине-истоку устанавливаем в ноль
	        $this->l[$source] = 0;
	        // отмечаем, что у вершины уже посещена и имеет постоянную метку
	        $this->visited[] = $source;
	    }

	    /*
	    * @param $source текущая вершина, которую мы обходим в конкретный момент
	    * @param $target конечная вершина, в которую мы должны прийти
	    * @param $count номер текущей итерации
	    * @param $is_path эта переменная определяет есть ли вообще маршрут,
	    * изначально подразумевается, что есть, но в процессе может выяснится,
	    * что нет
	    * @return в переменную result_q возвращается массив историй переходов
	    * */
	    public function shortestPath($source, $target, $count, &$is_path)
	    {
	        // обходим смежные вершины с текущей, смотрим если
	        // сумма метки текущей вершины + вес ребра < веса
	        // смежной вершины, то у смежной вершины устанавливаем
	        // вес в значение: вес текущей вершины + вес перехода
	        // а в массив $q для смежной вершины устанавливаем значение
	        // текущей вершины
	        if (!empty($this->graph[$source])){
	            foreach($this->graph[$source] as $v => $cost){
	                if (($this->l[$source] + $cost) < $this->l[$v]){
	                    $this->l[$v] = $this->l[$source] + $cost;
	                    $this->q[$v] = $source;
	                }
	            }
	        }

	        // проверяем текущий массив непостоянных меток всех вершин всего
	        // графа и находим ту вершину, переход в которую из текущей
	        // является минимальным согласно стоимости перехода(веса ребра)
	        $local_min_cost = INF;
	        $local_min_v = NULL;
	        foreach($this->l as $v => $cost){
	            if (!in_array($v, $this->visited)){
	                if ($cost < $local_min_cost){
	                    $local_min_cost = $cost;
	                    $local_min_v = $v;
	                }
	            }
	        }
	        // если ни одна смежная вершина не найдена
	        // на каком-то шаге, то пути нет
	        if ($local_min_v === NULL){
	            $is_path = false;
	        }
	        // отмечаем эту вершину как имеющую постоянную ветку
	        $this->visited[] = $local_min_v;
	        // увеличиваем шаг итерации
	        $count++;

	        if (!in_array($target, $this->visited) && $is_path){
	            // если конечная вершина ещё не находится в массиве тех вершин,
	            // которые имеют постоянную метку, то продолжаем действие алгоритма
	            $this->shortestPath($local_min_v, $target, $count, $is_path);
	        } else{
	            // иначе в переменную result_q возвращаем текущее значение q,
	            // которое содержит историю переходов
	            $this->result_q = $this->q;
	        }

	    }

	    /*
	    * @param $q массив вершин, полученный функцией shortestPath, то
	    * есть по сути это значение result_q графа
	    * @param $source начальная вершина, из которой начался путь
	    * @param $target конечная вершина, в которую мы должны прийти
	    * @param $path переменная, в которую будет храниться необходимая
	    * последовательность переходов
	    * @return массив переходов из конечной вершины в начальную, то есть
	    * по сути маршрут, но в обратном порядке
	    * */
	    public function shortestPathresult($q, $source, $target, &$path){
	        if (empty($path)){
	            $path[] = $target;
	            $target = $q[$target];
	            $this->shortestPathresult($q, $source, $target, $path);
	        } else{
	            if($target != $source){
	                $path[] = $target;
	                $target = $q[$target];
	                $this->shortestPathresult($q, $source, $target, $path);
	            } else{
	                $path[] = $source;
	            }
	        }
	    }

	}

	// граф представлен в виде списка смежности
	$graph = [
	    '1' => ['2' => 10, '3' => 6, '4' => 8],
	    '2' => ['4' => 5, '5' => 13, '7' => 11],
	    '3' => ['5' => 3],
	    '4' => ['3' => 2, '5' => 5, '6' => 7, '7' => 12],
	    '5' => ['6' => 9, '9' => 12],
	    '6' => ['8' => 8, '9' => 10],
	    '7' => ['6' => 4, '8' => 6, '9' => 16],
	    '8' => ['9' => 15],
	    '9' => [],
	];
	// начальная и конечная вершины
	$source = '1';
	$target = '9';

	$g = new MyDijkstra($graph, $source);


	// начинаем с первой итерации
	$count = 1;
	$is_path = true;
	$g->shortestPath($source, $target, $count, $is_path);

	if (!$is_path){
	    $result = "Из $source в $target пути нет";
	} else{
	    // здесь будет храниться конечный путь
	    $path = [];
	    $g->shortestPathresult($g->result_q, $source, $target, $path);
	    $path = array_reverse($path);

	    // формируем необходимые для вывода переменные
	    $result = 'Путь: ';
	    $cost = 0;
	    foreach($path as $key => $value){
	        $result .= $value;
	        if ($key < count($path) - 1){
	            $result .= " -> ";
	        }

	        if (isset($path[$key + 1])){
	            $cost += $graph[$value][$path[$key + 1]];
	        }
	    }

	    $result .= " Длина: ".$cost;
	}

	print $result;