<?php
 
error_reporting(-1);
/* http://d...content-available-to-author-only...2.net/ */
 
define('SUBWAY', "едешь на метро");
define('FOOT', "идешь пешком");
define('BUS', "едешь на автобусе");

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

/*Функция вывода пути.
*/
function printPath($startPoint, $endPoint, $shortestPath, $paths, $pointNames){

    $pathTransport = array(
        0   =>  array(
            1   =>  BUS,
            2   =>  SUBWAY    
            ),

        1   =>  array(
            0   =>  BUS,
            3   =>  SUBWAY
        ),

        2   =>  array(
            0   =>  BUS,
            5   =>  FOOT,
            11  =>  SUBWAY
        ),

        3   =>  array(
            1   =>  SUBWAY,
            4   =>  BUS,
            12  =>  SUBWAY
        ),

        4   =>  array(
            3   =>  BUS,
            11  =>  SUBWAY,
            9   =>  FOOT
        ),

        5   =>  array(
            2   =>  FOOT
        ),

        6   =>  array(
            7   =>  FOOT,
            11  =>  FOOT
        ),

        7   =>  array(
            8   =>  FOOT,
            11  =>  FOOT,
            6   =>  FOOT
        ),

        8   =>  array(
            7   =>  FOOT,
            9   =>  FOOT
        ),

        9   =>  array(
            4   =>  FOOT,
            8   =>  FOOT,
            10  =>  BUS
        ),

        10   =>  array(
            9   =>  BUS,
            12  =>  FOOT
        ),

        11   =>  array(
            4   =>  SUBWAY,
            12  =>  SUBWAY,
            7   =>  FOOT,
            2   =>  SUBWAY,
            6   =>  FOOT,
            13  =>  FOOT        
        ),

        12   =>  array(
            10  =>  FOOT,
            3   =>  SUBWAY,
            11  =>  SUBWAY,
            13  =>  SUBWAY,
            14  =>  SUBWAY,
            15  =>  SUBWAY
        ),

        13   =>  array(
            12  =>  SUBWAY,
            11  =>  FOOT,
            14  =>  SUBWAY
        ),

        14   =>  array(
            12  =>  SUBWAY,
            15  =>  SUBWAY,
            13  =>  SUBWAY
        ),

        15   =>  array(
            12  =>  SUBWAY,
            14  =>  SUBWAY        
        )
    );
    echo "Начальная точка: \"{$pointNames[$startPoint]}\"\n";
    $temp = $startPoint;
    if ($shortestPath != NULL) {
        $temp = $startPoint;
        foreach ($shortestPath as $node) {
            echo "Из нее {$pathTransport[$temp][$node]} до точки \"{$pointNames[$node]}\" {$paths[$temp][$node]} мин.\n";
            $temp = $node;
        }
    }
    echo "Из нее {$pathTransport[$temp][$endPoint]} до точки \"{$pointNames[$endPoint]}\" {$paths[$temp][$endPoint]} мин.\n";
    echo "В итоге ты попадешь в точку \"{$pointNames[$endPoint]}\" за {$paths[$startPoint][$endPoint]} мин. Приятной поездки!\n\n";
}

$pointNames = array(
    0    =>  'ст. м. Петроградская',
    1    =>  'ст. м. Чкаловская',
    2    =>  'ст. м. Горьковская',
    3    =>  'ст. м. Спортивная',
    4    =>  'ст. м. Василеостровская',
    5    =>  'Петропавловская крепость',
    6    =>  'Летний сад',
    7    =>  'Дворцовая площадь',
    8    =>  'Исакиевский собор',
    9    =>  'Новая Голландия',
    10   =>  'Дом Раскольникова',
    11   =>  'Гостиный Двор',
    12   =>  'Сенная Площадь',
    13   =>  'ст. м. Владимирская',
    14   =>  'Витебский вокзал',
    15   =>  'Технологический Институт'
);

$paths = array(
    0   =>  array(
        1    =>  10,
        2    =>  3
    ),
 
    1   =>  array(
        0    =>  10,
        3    =>  3
    ),
 
    2   =>  array(
        0    =>  3,
        5    =>  5,
        11   =>  6
    ),
 
    3   =>  array(
        1    =>  3,
        4    =>  10,
        12   =>  7
    ),
 
    4   =>  array(
        3    =>  10,
        11   =>  7,
        9    =>  11
    ),
 
    5   =>  array(
        2    =>  5
    ),
 
    6   =>  array(
        7    =>  6,
        11   =>  7
    ),
 
    7   =>  array(
        8    =>  6,
        11   =>  6,
        6    =>  6
    ),
 
    8   =>  array(
        7    =>  6,
        9    =>  5
    ),
 
    9   =>  array(
        4    =>  11,
        8    =>  5,
        10   =>  7
    ),
 
    10   =>  array(
        9    =>  7,
        12   =>  3
    ),
 
    11   =>  array(
        4    =>  7,
        12   =>  3,
        7    =>  6,
        2    =>  6,
        6    =>  7,
        13   =>  7        
    ),
 
    12   =>  array(
        10   =>  3,
        3    =>  7,
        11   =>  3,
        13   =>  4,
        14   =>  2,
        15   =>  3
    ),
 
    13   =>  array(
        12   =>  4,
        11   =>  7,
        14   =>  3
    ),
 
    14   =>  array(
        12   =>  2,
        15   =>  2,
        13   =>  3
    ),
 
    15   =>  array(
        12   =>  3,
        14   =>  2        
    )
);


$numberOfNodes = count($pointNames);

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

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


//Алгоритм Флойда-Уоршелла.

for ($k = 0; $k < $numberOfNodes; $k++) {
    for ($i = 0; $i < $numberOfNodes; $i++) {
        for ($j = 0; $j < $numberOfNodes; $j++) {
            if (($paths[$i][$k] + $paths[$k][$j]) < $paths[$i][$j]) {
                $paths[$i][$j] = $paths[$i][$k] + $paths[$k][$j];
                $interimStep[$i][$j] = $k;
            }
        }
    }
}


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

//ст. м. Петроградская -> Петропавловская крепость
$endPoint = 5;
$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 = 6;
$endPoint = 3;
$shortestPath = getPath($startPoint, $endPoint, $interimStep);
printPath($startPoint, $endPoint, $shortestPath, $paths, $pointNames);