<?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)
    ),
    'isa' => array(
        'dvo' => canGet(6, FOOT),
        'nov' => canGet(5, FOOT)
    ),

);

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

function makeOneMoreStep($paths, $pathDone, $time, $point, $target, $theNumbOf)
{
    $waysAndTimes[] = ['path' => null, 'time' => INF];
    if (array_key_exists($target, $paths[$point])) {
        $time += $paths[$point][$target]['time'];
        $pathDone[] = $target;
        $theNumbOf += 1;
        $waysAndTimes[] = ['path' => $pathDone, 'time' => $time];
    }
    foreach ($paths[$point] as $subTarget => $timeAndBy) {
        if (!in_array($subTarget, $pathDone) and !in_array($subTarget, $pathDone)) {
            list('path and time' => $waysAndTimes[], 'possible ways' => $theNumbOf) = makeOneMoreStep($paths, array_merge($pathDone, [$subTarget]), $time + $paths[$point][$subTarget]['time'], $subTarget, $target, $theNumbOf);

        }
    }
    return ['path and time' => bestPath($waysAndTimes), 'possible ways' => $theNumbOf];
}

function bestPath($waysAndTimes)
{
    $bestTime = INF;
    $bestPath = 0;
    foreach ($waysAndTimes as $pathNumber => $wayAndTime) {
        if ($wayAndTime['time'] < $bestTime) {
            $bestTime = $wayAndTime['time'];
            $bestPath = $pathNumber;
        }
    }
    return $waysAndTimes[$bestPath];
}

$point = 'pet'; // Старт
$target = 'nov'; // Финиш
$pathDone = [$point];
$time = 0;

print_r(makeOneMoreStep($paths, $pathDone, $time, $point, $target, 0));
$pathAndTimePossibleWays = makeOneMoreStep($paths, $pathDone, $time, $point, $target, 0);

$bestPath = $pathAndTimePossibleWays['path and time']['path'];
$bestTime = $pathAndTimePossibleWays['path and time']['time'];

echo "Начальная точка: $pointNames[$point]" . PHP_EOL;
for ($i = 0; $i < count($bestPath) - 1; $i++) {
    $a = $bestPath[$i];
    $b = $bestPath[$i + 1];
    echo "Из нее {$transportName[$paths[$a][$b]['by']]} до точки {$pointNames[$bestPath[$i+1]]} {$paths[$a][$b]['time']} мин" . PHP_EOL;
}
echo "В итоге ты попадешь в точку {$pointNames[$b]} за {$bestTime} минут ";