fork(1) download
copy 
  1. <?php
  2.  
  3. error_reporting(-1);
  4. /* http://d...content-available-to-author-only...2.net/ */
  5.  
  6. define('SUBWAY', "едешь на метро");
  7. define('FOOT', "идешь пешком");
  8. define('BUS', "едешь на автобусе");
  9.  
  10. /*Функция построения кратчайшего пути.
  11. Возвращает NULL, если кратчайший путь не содержит промежуточных нодов.
  12. Иначе, возвращает массив промежуточных нодов.
  13. */
  14. function getPath($start, $end, $interimStep){
  15.     if ($interimStep[$start][$end] == INF) {
  16.         return NULL;
  17.     }
  18.     $shortestPath = array();
  19.     $temp = $end;
  20.     while ($temp != INF) {
  21.         $temp = $interimStep[$start][$temp];
  22.         array_unshift($shortestPath, $temp);
  23.     }
  24.     unset($shortestPath[0]);
  25.     return $shortestPath;
  26. }
  27.  
  28. /*Функция вывода пути.
  29. */
  30. function printPath($startPoint, $endPoint, $shortestPath, $paths, $pointNames){
  31.  
  32.     $pathTransport = array(
  33.         0   =>  array(
  34.             1   =>  BUS,
  35.             2   =>  SUBWAY    
  36.             ),
  37.  
  38.         1   =>  array(
  39.             0   =>  BUS,
  40.             3   =>  SUBWAY
  41.         ),
  42.  
  43.         2   =>  array(
  44.             0   =>  BUS,
  45.             5   =>  FOOT,
  46.             11  =>  SUBWAY
  47.         ),
  48.  
  49.         3   =>  array(
  50.             1   =>  SUBWAY,
  51.             4   =>  BUS,
  52.             12  =>  SUBWAY
  53.         ),
  54.  
  55.         4   =>  array(
  56.             3   =>  BUS,
  57.             11  =>  SUBWAY,
  58.             9   =>  FOOT
  59.         ),
  60.  
  61.         5   =>  array(
  62.             2   =>  FOOT
  63.         ),
  64.  
  65.         6   =>  array(
  66.             7   =>  FOOT,
  67.             11  =>  FOOT
  68.         ),
  69.  
  70.         7   =>  array(
  71.             8   =>  FOOT,
  72.             11  =>  FOOT,
  73.             6   =>  FOOT
  74.         ),
  75.  
  76.         8   =>  array(
  77.             7   =>  FOOT,
  78.             9   =>  FOOT
  79.         ),
  80.  
  81.         9   =>  array(
  82.             4   =>  FOOT,
  83.             8   =>  FOOT,
  84.             10  =>  BUS
  85.         ),
  86.  
  87.         10   =>  array(
  88.             9   =>  BUS,
  89.             12  =>  FOOT
  90.         ),
  91.  
  92.         11   =>  array(
  93.             4   =>  SUBWAY,
  94.             12  =>  SUBWAY,
  95.             7   =>  FOOT,
  96.             2   =>  SUBWAY,
  97.             6   =>  FOOT,
  98.             13  =>  FOOT        
  99.         ),
  100.  
  101.         12   =>  array(
  102.             10  =>  FOOT,
  103.             3   =>  SUBWAY,
  104.             11  =>  SUBWAY,
  105.             13  =>  SUBWAY,
  106.             14  =>  SUBWAY,
  107.             15  =>  SUBWAY
  108.         ),
  109.  
  110.         13   =>  array(
  111.             12  =>  SUBWAY,
  112.             11  =>  FOOT,
  113.             14  =>  SUBWAY
  114.         ),
  115.  
  116.         14   =>  array(
  117.             12  =>  SUBWAY,
  118.             15  =>  SUBWAY,
  119.             13  =>  SUBWAY
  120.         ),
  121.  
  122.         15   =>  array(
  123.             12  =>  SUBWAY,
  124.             14  =>  SUBWAY        
  125.         )
  126.     );
  127.     echo "Начальная точка: \"{$pointNames[$startPoint]}\"\n";
  128.     $temp = $startPoint;
  129.     if ($shortestPath != NULL) {
  130.         $temp = $startPoint;
  131.         foreach ($shortestPath as $node) {
  132.             echo "Из нее {$pathTransport[$temp][$node]} до точки \"{$pointNames[$node]}\" {$paths[$temp][$node]} мин.\n";
  133.             $temp = $node;
  134.         }
  135.     }
  136.     echo "Из нее {$pathTransport[$temp][$endPoint]} до точки \"{$pointNames[$endPoint]}\" {$paths[$temp][$endPoint]} мин.\n";
  137.     echo "В итоге ты попадешь в точку \"{$pointNames[$endPoint]}\" за {$paths[$startPoint][$endPoint]} мин. Приятной поездки!\n\n";
  138. }
  139.  
  140. $pointNames = array(
  141.     0    =>  'ст. м. Петроградская',
  142.     1    =>  'ст. м. Чкаловская',
  143.     2    =>  'ст. м. Горьковская',
  144.     3    =>  'ст. м. Спортивная',
  145.     4    =>  'ст. м. Василеостровская',
  146.     5    =>  'Петропавловская крепость',
  147.     6    =>  'Летний сад',
  148.     7    =>  'Дворцовая площадь',
  149.     8    =>  'Исакиевский собор',
  150.     9    =>  'Новая Голландия',
  151.     10   =>  'Дом Раскольникова',
  152.     11   =>  'Гостиный Двор',
  153.     12   =>  'Сенная Площадь',
  154.     13   =>  'ст. м. Владимирская',
  155.     14   =>  'Витебский вокзал',
  156.     15   =>  'Технологический Институт'
  157. );
  158.  
  159. $paths = array(
  160.     0   =>  array(
  161.         1    =>  10,
  162.         2    =>  3
  163.     ),
  164.  
  165.     1   =>  array(
  166.         0    =>  10,
  167.         3    =>  3
  168.     ),
  169.  
  170.     2   =>  array(
  171.         0    =>  3,
  172.         5    =>  5,
  173.         11   =>  6
  174.     ),
  175.  
  176.     3   =>  array(
  177.         1    =>  3,
  178.         4    =>  10,
  179.         12   =>  7
  180.     ),
  181.  
  182.     4   =>  array(
  183.         3    =>  10,
  184.         11   =>  7,
  185.         9    =>  11
  186.     ),
  187.  
  188.     5   =>  array(
  189.         2    =>  5
  190.     ),
  191.  
  192.     6   =>  array(
  193.         7    =>  6,
  194.         11   =>  7
  195.     ),
  196.  
  197.     7   =>  array(
  198.         8    =>  6,
  199.         11   =>  6,
  200.         6    =>  6
  201.     ),
  202.  
  203.     8   =>  array(
  204.         7    =>  6,
  205.         9    =>  5
  206.     ),
  207.  
  208.     9   =>  array(
  209.         4    =>  11,
  210.         8    =>  5,
  211.         10   =>  7
  212.     ),
  213.  
  214.     10   =>  array(
  215.         9    =>  7,
  216.         12   =>  3
  217.     ),
  218.  
  219.     11   =>  array(
  220.         4    =>  7,
  221.         12   =>  3,
  222.         7    =>  6,
  223.         2    =>  6,
  224.         6    =>  7,
  225.         13   =>  7        
  226.     ),
  227.  
  228.     12   =>  array(
  229.         10   =>  3,
  230.         3    =>  7,
  231.         11   =>  3,
  232.         13   =>  4,
  233.         14   =>  2,
  234.         15   =>  3
  235.     ),
  236.  
  237.     13   =>  array(
  238.         12   =>  4,
  239.         11   =>  7,
  240.         14   =>  3
  241.     ),
  242.  
  243.     14   =>  array(
  244.         12   =>  2,
  245.         15   =>  2,
  246.         13   =>  3
  247.     ),
  248.  
  249.     15   =>  array(
  250.         12   =>  3,
  251.         14   =>  2        
  252.     )
  253. );
  254.  
  255.  
  256.  
  257. $numberOfNodes = count($pointNames);
  258.  
  259. /*Делаем квадратную матрицу путей размера $numberOfNodes, которая будет содержать время кратчайшего пути.
  260. Если путь не существует, то присваиваем ему значение бесконечности.
  261. */
  262. foreach ($paths as $i => $array) {
  263.     for ($j = 0; $j < $numberOfNodes; $j++) {
  264.         if (isset($paths[$i][$j]) == NULL) {
  265.             $paths[$i][$j] = INF;
  266.         }
  267.     }
  268. }
  269.  
  270. //Массив, который будет содержать предпоследний шаг кратчайшего пути.
  271. $interimStep = array();
  272. for ($i = 0; $i < $numberOfNodes; $i++) {
  273.     $interimStep[$i] = array_fill(0, $numberOfNodes, INF);
  274. }
  275.  
  276.  
  277. //Алгоритм Флойда-Уоршелла.
  278.  
  279. for ($k = 0; $k < $numberOfNodes; $k++) {
  280.     for ($i = 0; $i < $numberOfNodes; $i++) {
  281.         for ($j = 0; $j < $numberOfNodes; $j++) {
  282.             if (($paths[$i][$k] + $paths[$k][$j]) < $paths[$i][$j]) {
  283.                 $paths[$i][$j] = $paths[$i][$k] + $paths[$k][$j];
  284.                 $interimStep[$i][$j] = $k;
  285.             }
  286.         }
  287.     }
  288. }
  289.  
  290.  
  291.  
  292. //Тут вылетает предпоследняя нода (дом Раскольникова), но время всего пути выводится корректно.
  293. $startPoint = 0; // Петроградская
  294. $endPoint = 9; // Новая Голландия
  295. $shortestPath = getPath($startPoint, $endPoint, $interimStep);
  296. printPath($startPoint, $endPoint, $shortestPath, $paths, $pointNames);
  297.  
  298. //ст. м. Петроградская -> Петропавловская крепость
  299. $endPoint = 5;
  300. $shortestPath = getPath($startPoint, $endPoint, $interimStep);
  301. printPath($startPoint, $endPoint, $shortestPath, $paths, $pointNames);
  302.  
  303. /*Сенная Площадь -> Новая Голландия
  304. Тут все выводится корректно.
  305. */
  306. $startPoint = 12;
  307. $endPoint = 9;
  308. $shortestPath = getPath($startPoint, $endPoint, $interimStep);
  309. printPath($startPoint, $endPoint, $shortestPath, $paths, $pointNames);
  310.  
  311. //Летний сад -> ст. м. Спортивная
  312. $startPoint = 6;
  313. $endPoint = 3;
  314. $shortestPath = getPath($startPoint, $endPoint, $interimStep);
  315. printPath($startPoint, $endPoint, $shortestPath, $paths, $pointNames);
Success #stdin #stdout #stderr 0.01s 20520KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Начальная точка: "ст. м. Петроградская"
Из нее едешь на метро до точки "ст. м. Горьковская" 3 мин.
Из нее едешь на метро до точки "Гостиный Двор" 6 мин.
Из нее едешь на метро до точки "Сенная Площадь" 3 мин.
Из нее  до точки "Новая Голландия" 10 мин.
В итоге ты попадешь в точку "Новая Голландия" за 22 мин. Приятной поездки!

Начальная точка: "ст. м. Петроградская"
Из нее едешь на метро до точки "ст. м. Горьковская" 3 мин.
Из нее идешь пешком до точки "Петропавловская крепость" 5 мин.
В итоге ты попадешь в точку "Петропавловская крепость" за 8 мин. Приятной поездки!

Начальная точка: "Сенная Площадь"
Из нее идешь пешком до точки "Дом Раскольникова" 3 мин.
Из нее едешь на автобусе до точки "Новая Голландия" 7 мин.
В итоге ты попадешь в точку "Новая Голландия" за 10 мин. Приятной поездки!

Начальная точка: "Летний сад"
Из нее идешь пешком до точки "Гостиный Двор" 7 мин.
Из нее едешь на метро до точки "Сенная Площадь" 3 мин.
Из нее едешь на метро до точки "ст. м. Спортивная" 7 мин.
В итоге ты попадешь в точку "ст. м. Спортивная" за 17 мин. Приятной поездки!
stderr
copy 
PHP Notice:  Undefined offset: 9 in /home/VVocog/prog.php on line 136
https://ideone.com/CNhx9X
language:
PHP (php 7.3.5)
created:
10 years ago
visibility:
public

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!