<?php

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

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

$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' => ...), используем функцию. 
$inf = 99999;

$start = 'pet';
$end = 'nov';
$path = [$end];
$visited = [];
$time = [];

foreach($paths as $graph => $value) {
    $time[$graph] = $inf;
}
$time[$start] = 0;

function canGet($time, $byWhat) {
    return array('time' => $time, 'by' => $byWhat);
}

function findUnvisitedNodeWithLowestDistance($time, $visited) {
    foreach($time as $t => $value) {
        if(in_array($t, $visited)) {
            unset($time[$t]);
        }
    }
    return array_search(min($time), $time);
}
function Dijkstra($paths, $pos, $time, $visited, $start, $end, $path) {
    $visited[] = $pos;
    if(count($time) == count($visited)) {
        return findShortestPath($paths, $time, $end, $path, $start);
    }
    foreach ($paths[$pos] as $g => $v) {
        if ($time[$g] > $time[$pos] + $v['time']) {
            $time[$g] = $time[$pos] + $v['time'];
        }
    }
    $pos = findUnvisitedNodeWithLowestDistance($time, $visited);
    return Dijkstra($paths, $pos, $time, $visited, $start, $end, $path);
}
function findShortestPath($paths, $time, $pos, $path, $start) { //Проблема в этом алгоритме
    if($pos == $start) {
        $path = array_reverse($path);
        return $A = ['path' => $path, 'time' => $time];
    }
    foreach($paths[$pos] as $Graph => $value) {
        if($time[$pos] == $time[$Graph] + $value['time']) {
            $path[] = $Graph;
            $pos = $Graph;
            return findShortestPath($paths, $time, $pos, $path, $start);
        }
    }
}

$A = Dijkstra($paths, $start, $time, $visited, $start, $end, $path);
$path = $A['path'];
$time = $A['time'];

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