<?php // вычисление кратчайшего маршрута алгоритмом Дейкстры


error_reporting(-1);
define('SUBWAY', 'sub');
define('FOOT', 'foot');
define('BUS', 'bus');
 
$transportName = array(
    SUBWAY  =>  'едешь на метро',
    FOOT    =>  'идешь пешком',
    BUS     =>  'едешь на автобусе'
);
 
 
$startPoint = 'pet'; // начало маршрута
$endPoint = 'teh'; // конец маршрута
$infinity = 1000000; //вес маршрута соответствующий бесконечности

 
$pointNames = array(
    'pet'   =>  'ст. м. Петроградская',
    'chk'   =>  'ст. м. Чкаловская',
    'gor'   =>  'ст. м. Горьковская',
    'spo'   =>  'ст. м. Спортивная',
    'vas'   =>  'ст. м. Василеостровская',
    'kre'   =>  'Петропавловская крепость',
    'let'   =>  'Летний сад',
    'dvo'   =>  'Дворцовая площадь',
    'isa'   =>  'Исакиевский собор',
    'nov'   =>  'Новая Голландия',
    'ras'   =>  'Дом Раскольникова',
    'gos'   =>  'Гостиный Двор',
    'sen'   =>  'Сенная Площадь',
    'vla'   =>  'ст. м. Владимирская',
    'vit'   =>  'Витебский вокзал',
    'teh'   =>  'Технологический Институт'
);
 
$paths = array(
    'pet'   =>  array(
        'chk'   =>  canGet(10, BUS),
        'gor'   =>  canGet(3, SUBWAY)
    ),
 
    'chk'   =>  array(
        'pet'   =>  canGet(10, BUS),
        'spo'   =>  canGet(3, SUBWAY)
    ),
 
    'gor'   =>  array(
        'pet'   =>  canGet(3, BUS),
        'kre'   =>  canGet(5, FOOT),
        'gos'   =>  canGet(6, SUBWAY)
    ),
 
    'spo'   =>  array(
        'chk'   =>  canGet(3, SUBWAY),
        'vas'   =>  canGet(10, BUS),
        'sen'   =>  canGet(7, SUBWAY)
    ),
 
    'vas'   =>  array(
        'spo'   =>  canGet(10, BUS),
        'gos'   =>  canGet(7, SUBWAY),
        'nov'   =>  canGet(11, FOOT)
    ),
 
    'kre'   =>  array(
        'gor'   =>  canGet(5, FOOT)
    ),
 
    'let'   =>  array(
        'dvo'   =>  canGet(6, FOOT),
        'gos'   =>  canGet(7, FOOT)
    ),
 
    'dvo'   =>  array(
        'isa'   =>  canGet(6, FOOT),
        'gos'   =>  canGet(6, FOOT),
        'let'   =>  canGet(6, FOOT)
    ),
 
    'isa'   =>  array(
        'dvo'   =>  canGet(6, FOOT),
        'nov'   =>  canGet(5, FOOT)
    ),
 
    'nov'   =>  array(
        'vas'   =>  canGet(11, FOOT),
        'isa'   =>  canGet(5, FOOT),
        'ras'   =>  canGet(7, BUS)
    ),
 
    'ras'   =>  array(
        'nov'   =>  canGet(7, BUS),
        'sen'   =>  canGet(3, FOOT)
    ),
 
    'gos'   =>  array(
        'vas'   =>  canGet(7, SUBWAY),
        'sen'   =>  canGet(3, SUBWAY),
        'dvo'   =>  canGet(6, FOOT),
        'gor'   =>  canGet(6, SUBWAY),
        'let'   =>  canGet(7, FOOT),
        'vla'   =>  canGet(7, FOOT)        
    ),
 
    'sen'   =>  array(
        'ras'   =>  canGet(3, FOOT),
        'spo'   =>  canGet(7, SUBWAY),
        'gos'   =>  canGet(3, SUBWAY),
        'vla'   =>  canGet(4, SUBWAY),
        'vit'   =>  canGet(2, SUBWAY),
        'teh'   =>  canGet(3, SUBWAY)
    ),
 
    'vla'   =>  array(
        'sen'   =>  canGet(4, SUBWAY),
        'gos'   =>  canGet(7, FOOT),
        'vit'   =>  canGet(3, SUBWAY)
    ),
 
    'vit'   =>  array(
        'sen'   =>  canGet(2, SUBWAY),
        'teh'   =>  canGet(2, SUBWAY),
        'vla'   =>  canGet(3, SUBWAY)
    ),
 
    'teh'   =>  array(
        'sen'   =>  canGet(3, SUBWAY),
        'vit'   =>  canGet(2, SUBWAY)        
    )
);
 
/* Чтобы не писать много раз array('time' => ..., 'by' => ...), используем функцию. 
    «canGet» переводится как «можно попасть» */
function canGet($time, $byWhat) {
    return array('time'     =>  $time, 'by' =>  $byWhat);
}

function initialTime($pointName,$paths,$pointNames,$infinity){	//задаём время маршрутов, от выбраной точки до остальных, равным бесконечности
	foreach($pointNames as $name=>$nameLong){					//время движения от точки до неё самой равно 0
		if (array_key_exists($name,$paths[$pointName])){
			$pathArray[$name] = array('totalTime'=>$paths[$pointName][$name]['time'],'listOfRouts'=>array(1=>array($name,$paths[$pointName][$name]['time'],$paths[$pointName][$name]['by'])));	
		}
		elseif($name == $pointName){
			$pathArray[$name] = array('totalTime'=>0,'listOfRouts'=>array(1=>array($name,0,'Ты уже здесь.')));	
		}
		else{
			$pathArray[$name] = array('totalTime'=>$infinity,'listOfRouts'=>array());		
		}
	}
	return $pathArray;
}
function findLocalPointsTime($routs,$paths,$pointName){ 	//ищем время маршрутов от точки до её соседей
	$pathArrayInPoint = $routs;
	$pointContacts = $paths[$pointName];
	$pointTime = $routs[$pointName]['totalTime'];
	foreach($pointContacts as $name=>$routStat){
		$newTime = $pointTime + $routStat['time'];
		$oldTime = $routs[$name]['totalTime'];
		if($newTime<$oldTime){
			$pathArrayInPoint[$name]['totalTime'] = $newTime;
			$pathArrayInPoint[$name]['listOfRouts'] = $pathArrayInPoint[$pointName]['listOfRouts'];  
			$pathArrayInPoint[$name]['listOfRouts'][] = array($name,$routStat['time'],$routStat['by']); 
		}
	}
	return $pathArrayInPoint;
}

function printRout($startPoint,$fastRout,$pointNames){		//вывод информации о маршруте
	$start = $startPoint;
	foreach($fastRout as $i=>$routStat){
		switch ($routStat[2]){
			case "sub":
				$byWith = "на метро";
				break;
			case "foot":
				$byWith = "пешком";
				break;
			case "bus":		
				$byWith = "на автобусе";
				break;
		}
		$end = $routStat[0];
		echo "От $pointNames[$start] до $pointNames[$end] $routStat[1] мин. $byWith\n";
		$start = $end;
	}
}

//выбираем начальную точку
//задаём время движения до всех остальных точек бесконечным
//обходим все соседние точки и считаем время движения до них
//от каждой соседней точки обходим их соседние точки и считаем обзее время движения до них из первой точки

$listOfPoints = array($startPoint);
$listOfPoints2 = array();
$listOfCheckedPoint = array();

$routs = initialTime($startPoint,$paths,$pointNames,$infinity);
$n = 0;
while (isset($listOfPoints2)&&$n<10){
	foreach($listOfPoints as $i=>$name){
		if (!in_array($name,$listOfCheckedPoint)){
			$routs = findLocalPointsTime($routs,$paths,$name);	
			$listOfCheckedPoint[] = $name;
			$b = $paths[$name];
			foreach($b as $name2=>$longName){
				$listOfPoints2[] = $name2;
			}
		}
	}	
	$listOfPoints = $listOfPoints2;
	$listOfPoints2 = array();
	$n++;
}
echo "Путь от $pointNames[$startPoint] до $pointNames[$endPoint] займёт {$routs[$endPoint]['totalTime']} мин.\n";
echo "Маршрут:\n";
printRout($startPoint,$routs[$endPoint]['listOfRouts'],$pointNames);
echo "Приятной поездки!\n";