<?php

error_reporting(-1);

define('SUBWAY', 'sub');
define('FOOT', 'foot');
define('BUS', 'bus');

$transportName = array(
    SUBWAY => 'едешь на метро',
    FOOT => 'идешь пешком',
    BUS => 'едешь на автобусе'
);

$startPoint = 'pet'; // Петроградская
$endPoint = 'nov'; // Новая Голландия

$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 lowestWeightNode($weightOfActiveNodes)
{
    $lowestWeight = INF;
    $lowestNode = null;
    foreach ($weightOfActiveNodes as $node => $weightNode) {
        if ($lowestWeight > $weightNode) {
            $lowestWeight = $weightNode;
            $lowestNode = $node;
        }
    }
    return $lowestNode;
}

function searchForAWay($startPoint, $endPoint, $paths, $transportName, $pointNames)
{
    $point = array_keys($paths);
    $weightOfActiveNodes = array_fill_keys($point, INF); // Массив с весами узлов
    $parentsNode = array_fill_keys($point, '');; // Массив с родительскикими узлами
    $weightOfProcessedKnots = []; // Массив для обработаннхы узлов

    $weightOfActiveNodes[$startPoint] = 0; // Стартовой точке присваивается 0, для того, алгоритм поиска пути начался с неё
    $node = lowestWeightNode($weightOfActiveNodes); // Находит узел с наименьшим весом

    while ($node != $endPoint) {
        foreach ($paths[$node] as $neighbor => $timeAndBy) {
            if (array_key_exists($neighbor, $weightOfActiveNodes)) { // 
                $weightNeighbor = $weightOfActiveNodes[$node] + $timeAndBy['time']; // весСоседа = рассматриваемый узел + путь до соседа
                if ($weightOfActiveNodes[$neighbor] > $weightNeighbor) { // Если текущий вес узла (рассматриваемого соседа) больше чем , новый найденный
                    $parentsNode[$neighbor] = $node;
                    $weightOfActiveNodes[$neighbor] = $weightNeighbor;
                }
            }
        }
        $weightOfProcessedKnots[$node] = $weightOfActiveNodes[$node];
        unset($weightOfActiveNodes[$node]);
        $node = lowestWeightNode($weightOfActiveNodes);
    }

    $commonPath = []; // Кратчайший, требуемый путь
    $finishPoint = $endPoint;
    while ($finishPoint != $startPoint) {
        $commonPath[$finishPoint] = $parentsNode[$finishPoint];
        $finishPoint = $parentsNode[$finishPoint];
    }
    $commonPath = array_reverse($commonPath);

    #Вывод пути
    $totalTime = 0;
    foreach ($commonPath as $startPoint => $FinishPoint) {
        $wayOfMovement = $transportName[$paths[$startPoint][$FinishPoint]['by']];
        echo "Из неё {$wayOfMovement} до точки {$pointNames[$startPoint]} {$paths[$startPoint][$FinishPoint]['time']} мин." . PHP_EOL;
        $totalTime += $paths[$startPoint][$FinishPoint]['time'];
    }
    echo "В итоге ты попадешь в точку {$pointNames[$endPoint]} за {$totalTime} минут";
}

searchForAWay($startPoint, $endPoint, $paths, $transportName, $pointNames);