<?php

$paths = array(
    'pet'   =>  array(
    		'visited' 		=>  false,
    		'shortest_path' =>  INF,
    		'neighbors'     =>  array(
        		'chk'   =>  array('time'      => 10,
        						  'transport' => 'bus'),
        		'gor'   =>  array('time'      => 3,
        						  'transport' => 'sub'),
    	)
    ),

    'chk'   =>  array(
    		'visited' 		=>  false,
    		'shortest_path' =>  INF,
    		'neighbors'     =>  array(
        		'pet'   =>  array('time'      => 10,
        						  'transport' => 'bus'),
        		'spo'   =>  array('time'      => 3,
        						  'transport' => 'sub'),
    	)
    ),
    
    'gor'   =>  array(
    		'visited' 		=>  false,
    		'shortest_path' =>  INF,
    		'neighbors'     =>  array(
        		'pet'   =>  array('time'      => 3,
        						  'transport' => 'bus'),
        		'kre'   =>  array('time'      => 5,
        						  'transport' => 'foot'),
        		'gos'   =>  array('time'      => 6,
        						  'transport' => 'sub'),
    	)
    ),
    
    'spo'   =>  array(
    		'visited' 		=>  false,
    		'shortest_path' =>  INF,
    		'neighbors'     =>  array(
        		'chk'   =>  array('time'      => 3,
        						  'transport' => 'sub'),
        		'vas'   =>  array('time'      => 10,
        						  'transport' => 'bus'),
        		'sen'   =>  array('time'      => 7,
        						  'transport' => 'sub'),
    	)
    ),
    
    'vas'   =>  array(
    		'visited' 		=>  false,
    		'shortest_path' =>  INF,
    		'neighbors'     =>  array(
        		'spo'   =>  array('time'      => 10,
        						  'transport' => 'bus'),
        		'gos'   =>  array('time'      => 7,
        						  'transport' => 'sub'),
        		'nov'   =>  array('time'      => 11,
        						  'transport' => 'foot'),
    	)
    ),
    
    'kre'   =>  array(
    		'visited' 		=>  false,
    		'shortest_path' =>  INF,
    		'neighbors'     =>  array(
        		'gor'   =>  array('time'      => 5,
        						  'transport' => 'foot'),
    	)
    ),
    
    'let'   =>  array(
    		'visited' 		=>  false,
    		'shortest_path' =>  INF,
    		'neighbors'     =>  array(
        		'dvo'   =>  array('time'      => 6,
        						  'transport' => 'foot'),
        		'gos'   =>  array('time'      => 7,
        						  'transport' => 'foot'),
    	)
    ),
    
    'dvo'   =>  array(
    		'visited' 		=>  false,
    		'shortest_path' =>  INF,
    		'neighbors'     =>  array(
        		'isa'   =>  array('time'      => 6,
        						  'transport' => 'foot'),
        		'gos'   =>  array('time'      => 6,
        						  'transport' => 'foot'),
        		'let'   =>  array('time'      => 6,
        						  'transport' => 'foot'),
    	)
    ),
    
    'isa'   =>  array(
    		'visited' 		=>  false,
    		'shortest_path' =>  INF,
    		'neighbors'     =>  array(
        		'dvo'   =>  array('time'      => 6,
        						  'transport' => 'foot'),
        		'nov'   =>  array('time'      => 5,
        						  'transport' => 'foot'),
    	)
    ),
    
    'nov'   =>  array(
    		'visited' 		=>  false,
    		'shortest_path' =>  INF,
    		'neighbors'     =>  array(
        		'vas'   =>  array('time'      => 11,
        						  'transport' => 'foot'),
        		'isa'   =>  array('time'      => 5,
        						  'transport' => 'foot'),
        		'ras'   =>  array('time'      => 7,
        						  'transport' => 'bus'),
    	)
    ),
    
    'ras'   =>  array(
    		'visited' 		=>  false,
    		'shortest_path' =>  INF,
    		'neighbors'     =>  array(
        		'nov'   =>  array('time'      => 7,
        						  'transport' => 'bus'),
        		'sen'   =>  array('time'      => 3,
        						  'transport' => 'foot'),
    	)
    ),
    
    'gos'   =>  array(
    		'visited' 		=>  false,
    		'shortest_path' =>  INF,
    		'neighbors'     =>  array(
        		'vas'   =>  array('time'      => 7,
        						  'transport' => 'sub'),
        		'sen'   =>  array('time'      => 3,
        						  'transport' => 'sub'),
        		'dvo'   =>  array('time'      => 6,
        						  'transport' => 'foot'),
        		'gor'   =>  array('time'      => 6,
        						  'transport' => 'sub'),
        		'let'   =>  array('time'      => 7,
        						  'transport' => 'foot'),
        		'vla'   =>  array('time'      => 7,
        						  'transport' => 'foot'),    
    	)
    ),
    
    'sen'   =>  array(
    		'visited' 		=>  false,
    		'shortest_path' =>  INF,
    		'neighbors'     =>  array(
        		'ras'   =>  array('time'      => 3,
        						  'transport' => 'foot'),
        		'spo'   =>  array('time'      => 7,
        						  'transport' => 'sub'),
        		'gos'   =>  array('time'      => 3,
        						  'transport' => 'sub'),
        		'vla'   =>  array('time'      => 4,
        						  'transport' => 'sub'),
        		'vit'   =>  array('time'      => 2,
        						  'transport' => 'sub'),
        		'teh'   =>  array('time'      => 3,
        						  'transport' => 'sub'),
    	)
    ),
    
    'vla'   =>  array(
    		'visited' 		=>  false,
    		'shortest_path' =>  INF,
    		'neighbors'     =>  array(
        		'sen'   =>  array('time'      => 4,
        						  'transport' => 'sub'),
        		'gos'   =>  array('time'      => 7,
        						  'transport' => 'foot'),
        		'vit'   =>  array('time'      => 3,
        						  'transport' => 'sub'),
    	)
    ),
    
    'vit'   =>  array(
    		'visited' 		=>  false,
    		'shortest_path' =>  INF,
    		'neighbors'     =>  array(
        		'sen'   =>  array('time'      => 2,
        						  'transport' => 'sub'),
        		'teh'   =>  array('time'      => 2,
        						  'transport' => 'sub'),
        		'vla'   =>  array('time'      => 3,
        						  'transport' => 'sub'),
    	)
    ),

    'teh'   =>  array(
    		'visited' 		=>  false,
    		'shortest_path' =>  INF,
    		'neighbors'     =>  array(
        		'sen'   =>  array('time'      => 3,
        						  'transport' => 'sub'),
        		'vit'   =>  array('time'      => 2,
        						  'transport' => 'sub'),  
    	)
    )
);

function get_shortest_path($paths, $start_point, $end_point) // Получаем путь
 {	
 	
 	//Проверка на существование искомых вершин
 	if (array_key_exists($start_point, $paths)) {
 		if (array_key_exists($end_point, $paths)) {
 	 	
 		}else {
 	 	echo "Такой точки не существует $end_point \n";
 	 	return;
 		}
 	}else {
 		if (array_key_exists($end_point, $paths)) {
 	 	echo "Такой точки не существует $start_point \n";
 	 	return;
 		}else {
 	 	echo "Таких точек не существует $start_point, $end_point \n";
 	 	return;
 		}
 	}
 	
 	
 	 
 	
 	$current_point = $start_point;
 	// делаем длинну пути стартовой точки = 0
 	$paths[$current_point]['shortest_path'] = 0; 
	// циклим пока точка до которой мы идем не станет true
 	while ($paths[$end_point]['visited'] == false) { 
 		// смотрим соседей вершины и длинну пути и присваем if длина пути+пройденый путь меньше чем есть
 		$paths[$current_point]['visited'] = true; // ставим посещение true 
 		
 		foreach ($paths[$current_point]['neighbors'] as $name => $time_transport) { 
			if ($paths[$name]['visited'] == false) {
				$time = $time_transport['time'];
				if ($time+$paths[$current_point]['shortest_path'] < $paths[$name]['shortest_path']) {
					$paths[$name]['shortest_path'] = $time+$paths[$current_point]['shortest_path'];
				}
			} 
		}
		$min_path = INF; // переменная для сравнения
		// делаем старт поинт вершину с наименьшем пути
		foreach ($paths as  $name => $value) { 
			if ($paths[$name]['visited'] == false ) {
				if ($paths[$name]['shortest_path'] < $min_path) {
					$min_path = $paths[$name]['shortest_path'];
					$current_point = $name;
				}
			}
		}
 	}
 	return $paths;
}		

function print_shortest_path($paths, $start_point, $end_point) // Печатаем путь
{
	
	//Проверка на существование искомых вершин
 	if (array_key_exists($start_point, $paths)) {
 		if (array_key_exists($end_point, $paths)) {
 	 	
 		}else {
 	 	echo "Такой точки не существует $end_point \n";
 	 	return;
 		}
 	}else {
 		if (array_key_exists($end_point, $paths)) {
 	 	echo "Такой точки не существует $start_point \n";
 	 	return;
 		}else {
 	 	echo "Таких точек не существует $start_point, $end_point \n";
 	 	return;
 		}
 	}
	
	$transport_name = array(
				'sub' => 'Из неё едешь на метро',
				'foot' => 'Из неё идешь пешком',
				'bus' => 'Из неё едешь на автобусе'
	);
	$min_path = INF;
	$curent_point = $end_point;
    while ($curent_point != $start_point) {  // циклим пока не дойдем до начальной точки
    	$made_path[] = $curent_point;
    	foreach ($paths[$curent_point]['neighbors'] as  $name => $time_transport) { 
			if ($paths[$name]['visited'] == true ) {
				if ($paths[$name]['shortest_path'] < $min_path) {
					$transport_name = $time_transport['transport'];
					$min_path = $paths[$name]['shortest_path'];
					$curent_point = $name;
				}
			}
		}
    } 
    $made_path[] = $start_point;
    $made_path   = array_reverse ($made_path);
	echo "Начальная точка: $start_point\n";
	foreach ($made_path as $key => $path) {
		if ($key == 0 ) {
			continue;
		}
		$previous_point = $paths[$made_path[$key-1]];
		echo $transport_name[$previous_point['neighbors'][$path]['transport']]
		." до точки ".$path." за "
		.$previous_point['neighbors'][$path]['time']." мин.\n";
	}
	echo "В итоге ты попадешь в точку $end_point за ".$paths[$end_point]['shortest_path']." мин.\n";
}

$start_point = 'pet';
$end_point = 'nov';

$shortest_path = get_shortest_path($paths,$start_point, $end_point);
print_shortest_path($shortest_path,$start_point, $end_point);