<?php
 
error_reporting(-1);
/* http://d...content-available-to-author-only...2.net/ */

define('SUBWAY', "едешь на метро");
define('FOOT', "идешь пешком");
define('BUS', "едешь на автобусе");

define('P_PET', 0);
define('P_CHK', 1);
define('P_GOR', 2);
define('P_SPO', 3);
define('P_VAS', 4);
define('P_KRE', 5);
define('P_LET', 6);
define('P_DVO', 7);
define('P_ISA', 8);
define('P_NOV', 9);
define('P_RAS', 10);
define('P_GOS', 11);
define('P_SEN', 12);
define('P_VLA', 13);
define('P_VIT', 14);
define('P_TEH', 15);

define('PATH_TO_ITSELF', -1);

/* Чтобы не писать много раз array('time' => ..., 'by' => ...), используем функцию. 
    «canGet» переводится как «можно попасть» */
function canGet($time, $byWhat) {
    return array('time'     =>  $time, 'by' =>  $byWhat);
}

$pointNames = array(
    P_PET   =>  'ст. м. Петроградская',
    P_CHK   =>  'ст. м. Чкаловская',
    P_GOR   =>  'ст. м. Горьковская',
    P_SPO   =>  'ст. м. Спортивная',
    P_VAS   =>  'ст. м. Василеостровская',
    P_KRE   =>  'Петропавловская крепость',
    P_LET   =>  'Летний сад',
    P_DVO   =>  'Дворцовая площадь',
    P_ISA   =>  'Исакиевский собор',
    P_NOV   =>  'Новая Голландия',
    P_RAS   =>  'Дом Раскольникова',
    P_GOS   =>  'Гостиный Двор',
    P_SEN   =>  'Сенная Площадь',
    P_VLA   =>  'ст. м. Владимирская',
    P_VIT   =>  'Витебский вокзал',
    P_TEH   =>  'Технологический Институт'
);

$paths = array(
    P_PET   =>  array(
        P_CHK   =>  canGet(10, BUS),
        P_GOR   =>  canGet(3, SUBWAY)
    ),
 
    P_CHK   =>  array(
        P_PET   =>  canGet(10, BUS),
        P_SPO   =>  canGet(3, SUBWAY)
    ),
 
    P_GOR   =>  array(
        P_PET   =>  canGet(3, BUS),
        P_KRE   =>  canGet(5, FOOT),
        P_GOS   =>  canGet(6, SUBWAY)
    ),
 
    P_SPO   =>  array(
        P_CHK   =>  canGet(3, SUBWAY),
        P_VAS   =>  canGet(10, BUS),
        P_SEN   =>  canGet(7, SUBWAY)
    ),
 
    P_VAS   =>  array(
        P_SPO   =>  canGet(10, BUS),
        P_GOS   =>  canGet(7, SUBWAY),
        P_NOV   =>  canGet(11, FOOT)
    ),
 
    P_KRE   =>  array(
        P_GOR   =>  canGet(5, FOOT)
    ),
 
    P_LET   =>  array(
        P_DVO   =>  canGet(6, FOOT),
        P_GOS   =>  canGet(7, FOOT)
    ),
 
    P_DVO   =>  array(
        P_ISA   =>  canGet(6, FOOT),
        P_GOS   =>  canGet(6, FOOT),
        P_LET   =>  canGet(6, FOOT)
    ),
 
    P_ISA   =>  array(
        P_DVO   =>  canGet(6, FOOT),
        P_NOV   =>  canGet(5, FOOT)
    ),
 
    P_NOV   =>  array(
        P_VAS   =>  canGet(11, FOOT),
        P_ISA   =>  canGet(5, FOOT),
        P_RAS   =>  canGet(7, BUS)
    ),
 
    P_RAS   =>  array(
        P_NOV   =>  canGet(7, BUS),
        P_SEN   =>  canGet(3, FOOT)
    ),
 
    P_GOS   =>  array(
        P_VAS   =>  canGet(7, SUBWAY),
        P_SEN   =>  canGet(3, SUBWAY),
        P_DVO   =>  canGet(6, FOOT),
        P_GOR   =>  canGet(6, SUBWAY),
        P_LET   =>  canGet(7, FOOT),
        P_VLA   =>  canGet(7, FOOT)        
    ),
 
    P_SEN   =>  array(
        P_RAS   =>  canGet(3, FOOT),
        P_SPO   =>  canGet(7, SUBWAY),
        P_GOS   =>  canGet(3, SUBWAY),
        P_VLA   =>  canGet(4, SUBWAY),
        P_VIT   =>  canGet(2, SUBWAY),
        P_TEH   =>  canGet(3, SUBWAY)
    ),
 
    P_VLA   =>  array(
        P_SEN   =>  canGet(4, SUBWAY),
        P_GOS   =>  canGet(7, FOOT),
        P_VIT   =>  canGet(3, SUBWAY)
    ),
 
    P_VIT   =>  array(
        P_SEN   =>  canGet(2, SUBWAY),
        P_TEH   =>  canGet(2, SUBWAY),
        P_VLA   =>  canGet(3, SUBWAY)
    ),
 
    P_TEH   =>  array(
        P_SEN   =>  canGet(3, SUBWAY),
        P_VIT   =>  canGet(2, SUBWAY)        
    )
);
 

/*Функция построения кратчайшего пути.
Возвращает пустой массив, если кратчайший путь не содержит промежуточных нодов.
Иначе, возвращает массив промежуточных нодов.
*/
function getPath($start, $end, $interimStep){
    $shortestPath = array();
    $temp = $end;
    for ( ; $temp != $start; $temp = $interimStep[$start][$temp]) {
        array_unshift($shortestPath, $temp);
    }
    return $shortestPath;
}

/*
Функция вывода пути.
*/
function printPath($startPoint, $endPoint, $shortestPath, $paths, $pointNames, $pathCost){
    if ($startPoint == $endPoint) {
        echo "Ты собираешься попасть в точку, в которой уже находишься.(\"{$pointNames[$startPoint]}\")\n\n";
        return;
    }
    echo "Начальная точка: \"{$pointNames[$startPoint]}\"\n";
    $temp = $startPoint;
    foreach ($shortestPath as $node) {
        echo "Из нее {$paths[$temp][$node]['by']} до точки \"{$pointNames[$node]}\" {$pathCost[$temp][$node]} мин.\n";
        $temp = $node;
    }
    echo "В итоге ты попадешь в точку \"{$pointNames[$endPoint]}\" за {$pathCost[$startPoint][$endPoint]} мин. Приятной поездки!\n\n";
}

$numberOfNodes = count($pointNames);

/*
Делаем квадратную матрицу путей размера $numberOfNodes, которая будет содержать время кратчайшего пути.
Если путь не существует, то присваиваем ему значение бесконечности.

*/
$pathCost = array();
for ($i = 0; $i < $numberOfNodes; $i++) {
    for ($j = 0; $j < $numberOfNodes; $j++) {
        if ($i == $j) {
            $pathCost[$i][$j] = 0;
        } elseif (!isset($paths[$i][$j]['time'])) {
            $pathCost[$i][$j] = INF;
        } else {
            $pathCost[$i][$j] = $paths[$i][$j]['time'];
        }
    }
}

//Массив, который будет содержать предпоследний шаг кратчайшего пути.
$interimStep = array();
for ($i = 0; $i < $numberOfNodes; $i++) {
    $interimStep[$i] = array(); 
    for ($j = 0; $j < $numberOfNodes; $j++) {
        if ($i == $j) {
            $interimStep[$i][$j] = PATH_TO_ITSELF;
        } else {
            $interimStep[$i][$j] = $i;
        }
    }
}

//Алгоритм Флойда-Уоршелла.
for ($k = 0; $k < $numberOfNodes; $k++) {
    for ($i = 0; $i < $numberOfNodes; $i++) {
        for ($j = 0; $j < $numberOfNodes; $j++) {
            if (($pathCost[$i][$k] + $pathCost[$k][$j]) < $pathCost[$i][$j]) {
                $pathCost[$i][$j] = $pathCost[$i][$k] + $pathCost[$k][$j];
                $interimStep[$i][$j] = $interimStep[$k][$j];
            }
        }
    }
}

$startPoint = 0; // Петроградская
$endPoint = 9; // Новая Голландия
$shortestPath = getPath($startPoint, $endPoint, $interimStep);
printPath($startPoint, $endPoint, $shortestPath, $paths, $pointNames, $pathCost);

//Сенная Площадь -> Новая Голландия
$startPoint = 12;
$endPoint = 9;
$shortestPath = getPath($startPoint, $endPoint, $interimStep);
printPath($startPoint, $endPoint, $shortestPath, $paths, $pointNames, $pathCost);

$startPoint = P_VIT;
$endPoint = P_NOV;
$shortestPath = getPath($startPoint, $endPoint, $interimStep);
printPath($startPoint, $endPoint, $shortestPath, $paths, $pointNames, $pathCost);

$startPoint = P_LET;
$endPoint = P_KRE;
$shortestPath = getPath($startPoint, $endPoint, $interimStep);
printPath($startPoint, $endPoint, $shortestPath, $paths, $pointNames, $pathCost);

$startPoint = P_NOV;
$endPoint = P_NOV;
$shortestPath = getPath($startPoint, $endPoint, $interimStep);
printPath($startPoint, $endPoint, $shortestPath, $paths, $pointNames, $pathCost);

$startPoint = P_VAS;
$endPoint = P_NOV;
$shortestPath = getPath($startPoint, $endPoint, $interimStep);
printPath($startPoint, $endPoint, $shortestPath, $paths, $pointNames, $pathCost);