Посчитать минимальную стоимость пути из города А в город Б

$list_of_cities[1]- индекс города в массие
$list_of_cities[1]['neighbours'] - количесто маршрутов из города
$list_of_cities[1]['paths'][1] - первый маршрут и т.д.
nr -индекс города,к которому ведет маршрут
cost - условная стоимость маршрута к городу  индекс которого nr (из данного города)
 
//1 city data 'gdansk'
$list_of_cities[1]['city'] = 'gdansk';
$list_of_cities[1]['neighbours'] = 1;//city neighbours
$list_of_cities[1]['paths'][1] = array( 'nr'=>'2','cost'=>'1');//nr - index of a city connected ,cost - the transportation cost
$list_of_cities[1]['paths'][2] = array( 'nr'=>'3','cost'=>'3');
 
//2 city data 'bydgoszcz'
$list_of_cities[2]['city'] = 'bydgoszcz';
$list_of_cities[2]['neighbours'] = 3;
$list_of_cities[2]['paths'][1] = array( 'nr'=>'1','cost'=>'1');
$list_of_cities[2]['paths'][2] = array( 'nr'=>'3','cost'=>'1');
$list_of_cities[2]['paths'][3] = array( 'nr'=>'4','cost'=>'4');
 
//3 city data 'torun'
$list_of_cities[3]['city'] = 'torun';
$list_of_cities[3]['neighbours'] = 3;
$list_of_cities[3]['paths'][1] = array( 'nr'=>'1','cost'=>'3');
$list_of_cities[3]['paths'][2] = array( 'nr'=>'2','cost'=>'1');
$list_of_cities[3]['paths'][3] = array( 'nr'=>'4','cost'=>'1');
 
//4 city data 'warszawa'
$list_of_cities[4]['city'] = 'warszawa';
$list_of_cities[4]['neighbours'] = 2;
$list_of_cities[4]['paths'][1] = array( 'nr'=>'2','cost'=>'4');
$list_of_cities[4]['paths'][2] = array( 'nr'=>'3','cost'=>'1');

$all = []; // тута будем хранить все возможные пути
$data = [
  'Moscow' => [
    'to' => [
      'London' => '20 баксов',
      'Питер' => '5 баксов' и т.д.
     ]
  ]
];
 
 
/*
@$current_city - тута название текущего города, в котором мы находимся
@$destination_city - а тута тот город, куда хотим приехать
@$path - тут мы храним путь который мы уже прошли, например в массиве ['Москва', 'Лондон', 'Нью Васюки']
*/
 
function foo($current_city, $destination_city, $path) {
 
$path[] = $current_city; // добавим текущий город в пройденный путь
if($current_city == $destination_city) { // всё, на месте
  $all[] = $path; // сохраним путь
 return;
}
 
 
$c = $data[$current_city]; // взяли инфу по текущему городу
 
foreach($c['to'] as $name=>$value) { // проходимся по всем возможным пунктам назначения
 if(in_array($path, $name)) // если данный город мы уже посещали - то  не поеедм, иначе будем по кольцу ходить. порядок в in_array мог напутать, что там вначале, ключ или массив
   continue
 
  // если в данном городе еще не были - самое время посетить
 
  foo($name, $destination_city, $path); // поехали в следующий город
 
} 
 
}