Компонент Algorithm содержит класс Dijkstra для поиска самого дешевого маршрута, используя для этого алгоритм Дейкстры

Добавление в проект

composer require dolphin83/algorithm

Базовое использование

$departure = 'A';
$destination = 'C';
$map['A']['B'] = 2;
$map['A']['C'] = 7;
$map['A']['D'] = 5;
$map['B']['D'] = 3;
$map['C']['B'] = 3;
$map['D']['C'] = 1;

$res = Dijkstra::getCheapestRoute($departure, $destination, $map);

По умолчанию функция работает с существующей матрицей тарифов "как есть". Если, например, указана стоимость перемещения из города A в В, но не указана стоимость перемещения из В в А, функция считает что из А в В проехать можно, а в обратном направлении - нельзя и будет строить итоговый маршрут исходя из данного предположения.

Режим работы функции можно изменить, добавив четвертым параметром значение FALSE. Тогда при наличии информации о стоимости перемещения из А в В и отсутствии информации о стоимости обратного перемещения функция будет считать, что стоимость(A->B) = стоимость(B->A) и построит маршрут исходя из данного предположения.