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