<?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('UNKNOWN', -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)        
    )
);
 

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

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

$numberOfNodes = count($pointNames);

/*Делаем квадратную матрицу путей размера $numberOfNodes, которая будет содержать время кратчайшего пути.
Если путь не существует, то присваиваем ему значение бесконечности.
*/
foreach ($paths as $i => $array) {
    for ($j = 0; $j < $numberOfNodes; $j++) {
        if (isset($paths[$i][$j]['time']) == NULL) {
            $paths[$i][$j]['time'] = INF;
        }
    }
}

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

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

//Тут вылетает предпоследняя нода (дом Раскольникова), но время всего пути выводится корректно.
$startPoint = 0; // Петроградская
$endPoint = 9; // Новая Голландия
$shortestPath = getPath($startPoint, $endPoint, $interimStep);
printPath($startPoint, $endPoint, $shortestPath, $paths, $pointNames);

//Сенная Площадь -> Новая Голландия
//Тут все выводится корректно.
$startPoint = 12;
$endPoint = 9;
$shortestPath = getPath($startPoint, $endPoint, $interimStep);
printPath($startPoint, $endPoint, $shortestPath, $paths, $pointNames);

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

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