<?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) // Получаем путь
 {	
 	
 	foreach ($paths as $name => $value) { // Проверяем есть ли такие точки.
 		if ($start_point == $name) {
 			$check_start_point = true;
 		}elseif ($end_point == $name) {
 			$check_end_point = true;
 		}
 	}
 	if ($check_start_point != true) {
 		echo "Такой точки не существует ".$start_point;
 		return;
 	}elseif ($check_end_point != true) {
 		echo "Такой точки не существует ".$end_point;
 		return;
 	}
 	
 	
 	
 	$current_point = $start_point;
 	$paths[$current_point]['shortest_path'] = 0; // делаем длинну пути стартовой точки = 0
 	while ($paths[$end_point]['visited'] == false) { // циклим пока точка до которой мы идем не станет true
 		$paths[$current_point]['visited'] = true; // ставим посещение true 
 		foreach ($paths[$current_point]['neighbors'] as $name => $time_transport) { // смотрим соседей вершины и длинну пути и присваем if длина пути+пройденый путь меньше чем есть
			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'];
				}
			} 
		}
		$j = INF; // переменная для сравнения
		foreach ($paths as  $name => $value) { // делаем старт поинт вершину с наименьшем пути
			if ($paths[$name]['visited'] == false ) {
				if ($paths[$name]['shortest_path'] < $j) {
					$j = $paths[$name]['shortest_path'];
					$current_point = $name;
				}
			}
		}
 	}
 	print_shortest_path($paths, $start_point, $end_point);
}		

function print_shortest_path($paths, $start_point, $end_point) // Печатаем путь
{
	$transportName = array(
				'sub' => 'Из неё едешь на метро',
				'foot' => 'Из неё идешь пешком',
				'bus' => 'Из неё едешь на автобусе'
	);
	$j = INF;
	$curent_point = $end_point;
    while ($paths[$curent_point]['shortest_path'] != 0) {  // циклим пока не дойдем до начальной точки
    	$made_path[] = $curent_point;
    	foreach ($paths[$curent_point]['neighbors'] as  $name => $time_transport) { 
			if ($paths[$name]['visited'] == true ) {
				if ($paths[$name]['shortest_path'] < $j) {
					$transport_name = $time_transport['transport'];
					$j = $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 ($path == 'pet') {
			continue;
		}
		echo $transportName[$paths[$made_path[$key-1]]['neighbors'][$path]['transport']]
		." до точки ".$path." за "
		.$paths[$made_path[$key-1]]['neighbors'][$path]['time']." мин.\n";
	}
	echo "В итоге ты попадешь в точку $end_point за ".$paths[$end_point]['shortest_path']." мин.\n";
}

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

 get_shortest_path($paths,$start_point, $end_point);