fork download 
  1. <?php
  2.     error_reporting(-1);
  3.  
  4.     define('SUBWAY', 'sub');
  5.     define('FOOT', 'foot');
  6.     define('BUS', 'bus');
  7.  
  8.     $transportName = array(
  9.         SUBWAY  =>  'едешь на метро',
  10.         FOOT    =>  'идешь пешком',
  11.         BUS     =>  'едешь на автобусе'
  12.     );
  13.  
  14.     $startPoint = 'pet'; // Петроградская
  15.     $endPoint = 'nov'; // Новая Голландия
  16.  
  17.     $pointNames = array(
  18.         'pet'   =>  'ст. м. Петроградская',
  19.         'chk'   =>  'ст. м. Чкаловская',
  20.         'gor'   =>  'ст. м. Горьковская',
  21.         'spo'   =>  'ст. м. Спортивная',
  22.         'vas'   =>  'ст. м. Василеостровская',
  23.         'kre'   =>  'Петропавловская крепость',
  24.         'let'   =>  'Летний сад',
  25.         'dvo'   =>  'Дворцовая площадь',
  26.         'isa'   =>  'Исакиевский собор',
  27.         'nov'   =>  'Новая Голландия',
  28.         'ras'   =>  'Дом Раскольникова',
  29.         'gos'   =>  'Гостиный Двор',
  30.         'sen'   =>  'Сенная Площадь',
  31.         'vla'   =>  'ст. м. Владимирская',
  32.         'vit'   =>  'Витебский вокзал',
  33.         'teh'   =>  'Технологический Институт'
  34.     );
  35.  
  36.     $paths = array(
  37.         'pet'   =>  array(
  38.             'chk'   =>  canGet(10, BUS),
  39.             'gor'   =>  canGet(3, SUBWAY)
  40.         ),
  41.  
  42.         'chk'   =>  array(
  43.             'pet'   =>  canGet(10, BUS),
  44.             'spo'   =>  canGet(3, SUBWAY)
  45.         ),
  46.  
  47.         'gor'   =>  array(
  48.             'pet'   =>  canGet(3, BUS),
  49.             'kre'   =>  canGet(5, FOOT),
  50.             'gos'   =>  canGet(6, SUBWAY)
  51.         ),
  52.  
  53.         'spo'   =>  array(
  54.             'chk'   =>  canGet(3, SUBWAY),
  55.             'vas'   =>  canGet(10, BUS),
  56.             'sen'   =>  canGet(7, SUBWAY)
  57.         ),
  58.  
  59.         'vas'   =>  array(
  60.             'spo'   =>  canGet(10, BUS),
  61.             'gos'   =>  canGet(7, SUBWAY),
  62.             'nov'   =>  canGet(11, FOOT)
  63.         ),
  64.  
  65.         'kre'   =>  array(
  66.             'gor'   =>  canGet(5, FOOT)
  67.         ),
  68.  
  69.         'let'   =>  array(
  70.             'dvo'   =>  canGet(6, FOOT),
  71.             'gos'   =>  canGet(7, FOOT)
  72.         ),
  73.  
  74.         'dvo'   =>  array(
  75.             'isa'   =>  canGet(6, FOOT),
  76.             'gos'   =>  canGet(6, FOOT),
  77.             'let'   =>  canGet(6, FOOT)
  78.         ),
  79.  
  80.         'isa'   =>  array(
  81.             'dvo'   =>  canGet(6, FOOT),
  82.             'nov'   =>  canGet(5, FOOT)
  83.         ),
  84.  
  85.         'nov'   =>  array(
  86.             'vas'   =>  canGet(11, FOOT),
  87.             'isa'   =>  canGet(5, FOOT),
  88.             'ras'   =>  canGet(7, BUS)
  89.         ),
  90.  
  91.         'ras'   =>  array(
  92.             'nov'   =>  canGet(7, BUS),
  93.             'sen'   =>  canGet(3, FOOT)
  94.         ),
  95.  
  96.         'gos'   =>  array(
  97.             'vas'   =>  canGet(7, SUBWAY),
  98.             'sen'   =>  canGet(3, SUBWAY),
  99.             'dvo'   =>  canGet(6, FOOT),
  100.             'gor'   =>  canGet(6, SUBWAY),
  101.             'let'   =>  canGet(7, FOOT),
  102.             'vla'   =>  canGet(7, FOOT)        
  103.         ),
  104.  
  105.         'sen'   =>  array(
  106.             'ras'   =>  canGet(3, FOOT),
  107.             'spo'   =>  canGet(7, SUBWAY),
  108.             'gos'   =>  canGet(3, SUBWAY),
  109.             'vla'   =>  canGet(4, SUBWAY),
  110.             'vit'   =>  canGet(2, SUBWAY),
  111.             'teh'   =>  canGet(3, SUBWAY)
  112.         ),
  113.  
  114.         'vla'   =>  array(
  115.             'sen'   =>  canGet(4, SUBWAY),
  116.             'gos'   =>  canGet(7, FOOT),
  117.             'vit'   =>  canGet(3, SUBWAY)
  118.         ),
  119.  
  120.         'vit'   =>  array(
  121.             'sen'   =>  canGet(2, SUBWAY),
  122.             'teh'   =>  canGet(2, SUBWAY),
  123.             'vla'   =>  canGet(3, SUBWAY)
  124.         ),
  125.  
  126.         'teh'   =>  array(
  127.             'sen'   =>  canGet(3, SUBWAY),
  128.             'vit'   =>  canGet(2, SUBWAY)        
  129.         )
  130.     );
  131.  
  132.     function canGet($time, $byWhat) 
  133.     {
  134.         return array('time'     =>  $time, 'by' =>  $byWhat);
  135.     }
  136.  
  137.     /**
  138.      *  Функция для инициализации начальных данных
  139.      * 
  140.      *  Функция принимает на вход начальную вершину, создает массивы для меток вершин
  141.      *  и фиксирования посещения вершины, и возвращает их
  142.      *
  143.      *  @global array $paths      Глобальный массив вершин
  144.      *  @param string $startPoint Начальная вершина
  145.      *  @return array             Чистый массив меток и посещений
  146.      */
  147.     function initAlgorithm($startPoint)
  148.     {
  149.         global $paths;
  150.  
  151.         /** Массив фиксирующий посещение метки */
  152.         $visited = array();
  153.  
  154.         /** Массив меток для вершин. Метка начальной вершины - 0, остальный - inf */
  155.         $labels = array();
  156.  
  157.         foreach ($paths as $point => $pointValue) {
  158.             $labels[$point] = PHP_INT_MAX;
  159.             $visited[$point] = false;
  160.         }
  161.         $labels[$startPoint] = 0;
  162.  
  163.         $result = array();
  164.         $result['labels'] = $labels;
  165.         $result['visited'] = $visited;
  166.  
  167.         return $result;
  168.     }
  169.  
  170.     /**
  171.      *  Функция выполняющая алгоритм Дейскры
  172.      *
  173.      *  @global $paths          Глобальный массив вершин
  174.      *  @param array $labels    Массив меток вершин
  175.      *  @param array $visited   Массив посещения вершин
  176.      *  @return array
  177.      */
  178.     function doAlgorithmDijstra($labels, $visited)
  179.     {
  180.         global $paths;
  181.  
  182.         /** Количество вершин */
  183.         $countPoint = count($paths);
  184.  
  185.         for ($i = 0; $i < $countPoint; $i++) {
  186.  
  187.             /** Поиск вершины с наименьшей меткой */
  188.             $minLabel = PHP_INT_MAX;
  189.  
  190.             /** Вершина с которой работаем в данный момент */
  191.             $workPoint = NULL;
  192.  
  193.             foreach ($labels as $label => $value) {
  194.                 if (($value < $minLabel) && (!$visited[$label])) {
  195.                     $minLabel = $value;
  196.                     $workPoint = $label;
  197.                 }
  198.             }
  199.  
  200.             /** Получение всех вершин, которые соединяются с текущей */
  201.             $nextPoint = $paths[$workPoint];
  202.  
  203.             /** Перерасчет меток соседних вершин */
  204.             foreach ($nextPoint as $point => $valuePoint) {
  205.                 $newLabel = $labels[$workPoint] + $nextPoint[$point]['time'];
  206.                 if ($labels[$point] > $newLabel) {
  207.                     $labels[$point] = $newLabel;
  208.                 }
  209.             }
  210.  
  211.             /** Помечаем вершину, как посещенную */
  212.             $visited[$workPoint] = true;
  213.         }
  214.  
  215.         return $labels;
  216.     }
  217.  
  218.     /**
  219.      *  Функция восстановления пути по массиву меток
  220.      *
  221.      *  @global $paths            Глобальный массив вершин
  222.      *  @param string $startPoint Начальная вершина
  223.      *  @param string $endPoint   Конечная вершина
  224.      *  @param array $labels      Массив меток вершин
  225.      *  @return array             Искомый путь
  226.      */
  227.     function restorationPath($startPoint, $endPoint, $labels)
  228.     {
  229.         global $paths;
  230.  
  231.         /** Текущая вершина */
  232.         $currentPoint = $endPoint;
  233.         $targetPath = array($currentPoint);
  234.  
  235.         while ($currentPoint != $startPoint) {
  236.             foreach ($paths[$currentPoint] as $nextPoint => $nextPointValue) {
  237.                 if ($labels[$currentPoint] - $paths[$currentPoint][$nextPoint]['time'] == $labels[$nextPoint]) {
  238.                     $targetPath[] = $nextPoint;
  239.                     $currentPoint = $nextPoint;
  240.                     break;
  241.                 }
  242.             }
  243.         }
  244.  
  245.         $targetPath = array_reverse($targetPath);
  246.         return $targetPath;
  247.     }
  248.  
  249.  
  250.     /**
  251.      *  Функция печати оптимального пути
  252.      *
  253.      *  Функция принимает начальную и конечную вершину пути, 
  254.      *  массив меток, массив оптимального пути, и выводит последний
  255.      *
  256.      *  @global $paths             Глобальный массив вершин
  257.      *  @global $pointNames        Глобальный массив "человеческих" названий вершин
  258.      *  @global $transportName     Глобальны массив передвижения из точки А в точку Б
  259.      *  @param string $startPoint  Начальная вершина
  260.      *  @param string $endPoint    Конечная вершина
  261.      *  @param array $targetPath   Массив оптимального пути
  262.      *  @param array $finalLabel   Массив итоговых меток
  263.      *  @return void
  264.      */
  265.     function printTargetPath($startPoint, $endPoint, $targetPath, $finalLabel)
  266.     {
  267.         global $paths;
  268.         global $pointNames;
  269.         global $transportName;
  270.  
  271.         $countTargetPoint = count($targetPath);
  272.  
  273.         echo "Начальная точка: {$pointNames[$startPoint]}\n";
  274.         for ($i = 0; $i < $countTargetPoint - 1; $i++) {
  275.             /** Определение випа транспорта */
  276.             $nmtransport = $transportName[$paths[$targetPath[$i]][$targetPath[$i + 1]]['by']];
  277.             echo "Из нее {$nmtransport} до точки {$pointNames[$targetPath[$i + 1]]} {$paths[$targetPath[$i]][$targetPath[$i + 1]]['time']} минут\n";
  278.         }
  279.         echo "В итоге ты попадаешь в точку " . $pointNames[$endPoint] . " за " . $finalLabel[$endPoint] . " минут. Приятной поездки!" ;
  280.     }
  281.  
  282.     /** Массив меток и посещений*/
  283.     $cleanLabel = array();
  284.     $cleanLabel = initAlgorithm($startPoint);
  285.  
  286.     /** Результат работы алгоритма */
  287.     $finalLabel = array();
  288.     $finalLabel =  doAlgorithmDijstra($cleanLabel['labels'], $cleanLabel['visited']);
  289.  
  290.     /** Оптимальный путь */
  291.     $targetPath = array();
  292.     $targetPath = restorationPath($startPoint, $endPoint, $finalLabel);
  293.     printTargetPath($startPoint, $endPoint, $targetPath, $finalLabel);
  294. ?>
Success #stdin #stdout 0.01s 52488KB
comments (?)
stdin 
Standard input is empty
stdout 
Начальная точка: ст. м. Петроградская
Из нее едешь на метро до точки ст. м. Горьковская 3 минут
Из нее едешь на метро до точки Гостиный Двор 6 минут
Из нее едешь на метро до точки Сенная Площадь 3 минут
Из нее идешь пешком до точки Дом Раскольникова 3 минут
Из нее едешь на автобусе до точки Новая Голландия 7 минут
В итоге ты попадаешь в точку Новая Голландия за 22 минут. Приятной поездки!
https://ideone.com/0SJSa0
language:
PHP (php 7.3.5)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!