<?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)        
        )
    );

    function canGet($time, $byWhat) 
    {
        return array('time'     =>  $time, 'by' =>  $byWhat);
    }
    
    /**
     *  Функция для инициализации начальных данных
     * 
     *  Функция принимает на вход начальную вершину, создает массивы для меток вершин
     *  и фиксирования посещения вершины, и возвращает их
     *
     *  @global array $paths      Глобальный массив вершин
     *  @param string $startPoint Начальная вершина
     *  @return array             Чистый массив меток и посещений
     */
    function initAlgorithm($startPoint)
    {
        global $paths;

        /** Массив фиксирующий посещение метки */
        $visited = array();
        
        /** Массив меток для вершин. Метка начальной вершины - 0, остальный - inf */
        $labels = array();
        
        foreach ($paths as $point => $pointValue) {
            $labels[$point] = PHP_INT_MAX;
            $visited[$point] = false;
        }
        $labels[$startPoint] = 0;
        
        $result = array();
        $result['labels'] = $labels;
        $result['visited'] = $visited;
        
        return $result;
    }
     
    /**
     *  Функция выполняющая алгоритм Дейскры
     *
     *  @global $paths          Глобальный массив вершин
     *  @param array $labels    Массив меток вершин
     *  @param array $visited   Массив посещения вершин
     *  @return array
     */
    function doAlgorithmDijstra($labels, $visited)
    {
        global $paths;
        
        /** Количество вершин */
        $countPoint = count($paths);
        
        for ($i = 0; $i < $countPoint; $i++) {
            
            /** Поиск вершины с наименьшей меткой */
            $minLabel = PHP_INT_MAX;
            
            /** Вершина с которой работаем в данный момент */
            $workPoint = NULL;
            
            foreach ($labels as $label => $value) {
                if (($value < $minLabel) && (!$visited[$label])) {
                    $minLabel = $value;
                    $workPoint = $label;
                }
            }
            
            /** Получение всех вершин, которые соединяются с текущей */
            $nextPoint = $paths[$workPoint];
            
            /** Перерасчет меток соседних вершин */
            foreach ($nextPoint as $point => $valuePoint) {
                $newLabel = $labels[$workPoint] + $nextPoint[$point]['time'];
                if ($labels[$point] > $newLabel) {
                    $labels[$point] = $newLabel;
                }
            }
            
            /** Помечаем вершину, как посещенную */
            $visited[$workPoint] = true;
        }
        
        return $labels;
    }

    /**
     *  Функция восстановления пути по массиву меток
     *
     *  @global $paths            Глобальный массив вершин
     *  @param string $startPoint Начальная вершина
     *  @param string $endPoint   Конечная вершина
     *  @param array $labels      Массив меток вершин
     *  @return array             Искомый путь
     */
    function restorationPath($startPoint, $endPoint, $labels)
    {
        global $paths;
        
        /** Текущая вершина */
        $currentPoint = $endPoint;
        $targetPath = array($currentPoint);
        
        while ($currentPoint != $startPoint) {
            foreach ($paths[$currentPoint] as $nextPoint => $nextPointValue) {
                if ($labels[$currentPoint] - $paths[$currentPoint][$nextPoint]['time'] == $labels[$nextPoint]) {
                    $targetPath[] = $nextPoint;
                    $currentPoint = $nextPoint;
                    break;
                }
            }
        }
        
        $targetPath = array_reverse($targetPath);
        return $targetPath;
    }
    

    /**
     *  Функция печати оптимального пути
     *
     *  Функция принимает начальную и конечную вершину пути, 
     *  массив меток, массив оптимального пути, и выводит последний
     *
     *  @global $paths             Глобальный массив вершин
     *  @global $pointNames        Глобальный массив "человеческих" названий вершин
     *  @global $transportName     Глобальны массив передвижения из точки А в точку Б
     *  @param string $startPoint  Начальная вершина
     *  @param string $endPoint    Конечная вершина
     *  @param array $targetPath   Массив оптимального пути
     *  @param array $finalLabel   Массив итоговых меток
     *  @return void
     */
    function printTargetPath($startPoint, $endPoint, $targetPath, $finalLabel)
    {
        global $paths;
        global $pointNames;
        global $transportName;
        
        $countTargetPoint = count($targetPath);
    
        echo "Начальная точка: {$pointNames[$startPoint]}\n";
        for ($i = 0; $i < $countTargetPoint - 1; $i++) {
            /** Определение випа транспорта */
            $nmtransport = $transportName[$paths[$targetPath[$i]][$targetPath[$i + 1]]['by']];
            echo "Из нее {$nmtransport} до точки {$pointNames[$targetPath[$i + 1]]} {$paths[$targetPath[$i]][$targetPath[$i + 1]]['time']} минут\n";
        }
        echo "В итоге ты попадаешь в точку " . $pointNames[$endPoint] . " за " . $finalLabel[$endPoint] . " минут. Приятной поездки!" ;
    }
      
    /** Массив меток и посещений*/
    $cleanLabel = array();
    $cleanLabel = initAlgorithm($startPoint);
    
    /** Результат работы алгоритма */
    $finalLabel = array();
    $finalLabel =  doAlgorithmDijstra($cleanLabel['labels'], $cleanLabel['visited']);
    
    /** Оптимальный путь */
    $targetPath = array();
    $targetPath = restorationPath($startPoint, $endPoint, $finalLabel);
    printTargetPath($startPoint, $endPoint, $targetPath, $finalLabel);
?>