<?php

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

    'chk'   =>  array(
    		'visited' 		=>  false,
    		'shortest_path' =>  INF,
    		'from' 		    =>  '',
    		'neighbors'     =>  array(
        		'pet'   =>  array('time'      => 10,
        						  'transport' => 'bus'),
        		'spo'   =>  array('time'      => 3,
        						  'transport' => 'sub'),
    	)
    ),
    
    'gor'   =>  array(
    		'visited' 		=>  false,
    		'shortest_path' =>  INF,
    		'from' 		    =>  '',
    		'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,
    		'from' 		    =>  '',
    		'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,
    		'from' 		    =>  '',
    		'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,
    		'from' 		    =>  '',
    		'neighbors'     =>  array(
        		'gor'   =>  array('time'      => 5,
        						  'transport' => 'foot'),
    	)
    ),
    
    'let'   =>  array(
    		'visited' 		=>  false,
    		'shortest_path' =>  INF,
    		'from' 		    =>  '',
    		'neighbors'     =>  array(
        		'dvo'   =>  array('time'      => 6,
        						  'transport' => 'foot'),
        		'gos'   =>  array('time'      => 7,
        						  'transport' => 'foot'),
    	)
    ),
    
    'dvo'   =>  array(
    		'visited' 		=>  false,
    		'shortest_path' =>  INF,
    		'from' 		    =>  '',
    		'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,
    		'from' 		    =>  '',
    		'neighbors'     =>  array(
        		'dvo'   =>  array('time'      => 6,
        						  'transport' => 'foot'),
        		'nov'   =>  array('time'      => 5,
        						  'transport' => 'foot'),
    	)
    ),
    
    'nov'   =>  array(
    		'visited' 		=>  false,
    		'shortest_path' =>  INF,
    		'from' 		    =>  '',
    		'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,
    		'from' 		    =>  '',
    		'neighbors'     =>  array(
        		'nov'   =>  array('time'      => 7,
        						  'transport' => 'bus'),
        		'sen'   =>  array('time'      => 3,
        						  'transport' => 'foot'),
    	)
    ),
    
    'gos'   =>  array(
    		'visited' 		=>  false,
    		'shortest_path' =>  INF,
    		'from' 		    =>  '',
    		'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,
    		'from' 		    =>  '',
    		'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,
    		'from' 		    =>  '',
    		'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,
    		'from' 		    =>  '',
    		'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,
    		'from' 		    =>  '',
    		'neighbors'     =>  array(
        		'sen'   =>  array('time'      => 3,
        						  'transport' => 'sub'),
        		'vit'   =>  array('time'      => 2,
        						  'transport' => 'sub'),  
    	)
    )
);

$start_point = pet;
$end_point = nov;
 

 function asd($paths,$start_point,$end_point)
 {	
 	$constant_start_point = $start_point;
 	$constant_end_point   = $end_point;
 	$transportName = array(
				sub => 'Из неё едешь на метро',
				foot => 'Из неё идешь пешком',
				bus => 'Из неё едешь на автобусе'
	);
 	$shortest_path = $paths[$start_point]['shortest_path'];
 	$paths[$start_point]['shortest_path'] = 0; // делаем длинну пути стартовой точки = 0
 	$paths[$start_point]['from'] = 'start';
 	while ($paths[$end_point]['visited'] == false) { // циклим пока точка до которой мы идем не станет true
 		$paths[$start_point]['visited'] = true; // ставим посещение true 
 		foreach ($paths[$start_point]['neighbors'] as $name => $time_transport) { // смотрим соседей вершины и длинну пути и присваем if длина пути+пройденый путь меньше чем есть
			if ($paths[$name]['visited'] == false) {
				$time = $time_transport['time'];
				if ($time+$paths[$start_point]['shortest_path'] < $paths[$name]['shortest_path']) {
					$paths[$name]['shortest_path'] = $time+$paths[$start_point]['shortest_path'];
					$paths[$name]['from'] = $start_point;
				}
			} 
		}
		$j = INF;
		foreach ($paths as  $name => $value) { // делаем старт поинт вершину с наименьшем пути
			if ($paths[$name]['visited'] == false ) {
				if ($paths[$name]['shortest_path'] < $j) {
					$j = $paths[$name]['shortest_path'];
					$start_point = $name;
				}
			}
		}
 	}
    while ($paths[$end_point]['from'] != 'start') {  // циклим пока не дойдем до начальной точки
    	$faster_paths[] = $end_point;
    	$end_point = $paths[$end_point]['from'];
    } 
 	krsort($faster_paths); // сортируем что бы по порядку шёл
 	echo "Начальная точка: $constant_start_point\n";
	foreach ($faster_paths as $path) {
		echo $transportName[$paths[$paths[$path]['from']]['neighbors'][$path]['transport']]." до точки ".$path." за ".$paths[$paths[$path]['from']]['neighbors'][$path]['time']." мин.\n";
	}
	echo "В итоге ты попадешь в точку $constant_end_point за ".$paths[$constant_end_point]['shortest_path']." минут.";
}		


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