fork download 
  1. <?php
  2.  
  3. define('SUBWAY', 'sub');
  4. define('FOOT', 'foot');
  5. define('BUS', 'bus');
  6.  
  7. $transportName = array(
  8.     SUBWAY => 'едешь на метро',
  9.     FOOT => 'идешь пешком',
  10.     BUS => 'едешь на автобусе'
  11. );
  12.  
  13. $pointNames = array(
  14.     'pet' => 'ст. м. Петроградская',
  15.     'chk' => 'ст. м. Чкаловская',
  16.     'gor' => 'ст. м. Горьковская',
  17.     'spo' => 'ст. м. Спортивная',
  18.     'vas' => 'ст. м. Василеостровская',
  19.     'kre' => 'Петропавловская крепость',
  20.     'let' => 'Летний сад',
  21.     'dvo' => 'Дворцовая площадь',
  22.     'isa' => 'Исакиевский собор',
  23.     'nov' => 'Новая Голландия',
  24.     'ras' => 'Дом Раскольникова',
  25.     'gos' => 'Гостиный Двор',
  26.     'sen' => 'Сенная Площадь',
  27.     'vla' => 'ст. м. Владимирская',
  28.     'vit' => 'Витебский вокзал',
  29.     'teh' => 'Технологический Институт'
  30. );
  31.  
  32. $paths = array(
  33.     'pet' => array(
  34.         'chk' => canGet(10, BUS),
  35.         'gor' => canGet(3, SUBWAY)
  36.     ),
  37.     'chk' => array(
  38.         'pet' => canGet(10, BUS),
  39.         'spo' => canGet(3, SUBWAY)
  40.     ),
  41.     'gor' => array(
  42.         'pet' => canGet(3, BUS),
  43.         'kre' => canGet(5, FOOT),
  44.         'gos' => canGet(6, SUBWAY)
  45.     ),
  46.     'spo' => array(
  47.         'chk' => canGet(3, SUBWAY),
  48.         'vas' => canGet(10, BUS),
  49.         'sen' => canGet(7, SUBWAY)
  50.     ),
  51.     'vas' => array(
  52.         'spo' => canGet(10, BUS),
  53.         'gos' => canGet(7, SUBWAY),
  54.         'nov' => canGet(11, FOOT)
  55.     ),
  56.     'kre' => array(
  57.         'gor' => canGet(5, FOOT)
  58.     ),
  59.     'let' => array(
  60.         'dvo' => canGet(6, FOOT),
  61.         'gos' => canGet(7, FOOT)
  62.     ),
  63.     'dvo' => array(
  64.         'isa' => canGet(6, FOOT),
  65.         'gos' => canGet(6, FOOT),
  66.         'let' => canGet(6, FOOT)
  67.     ),
  68.     'isa' => array(
  69.         'dvo' => canGet(6, FOOT),
  70.         'nov' => canGet(5, FOOT)
  71.     ),
  72.     'nov' => array(
  73.         'vas' => canGet(11, FOOT),
  74.         'isa' => canGet(5, FOOT),
  75.         'ras' => canGet(7, BUS)
  76.     ),
  77.     'ras' => array(
  78.         'nov' => canGet(7, BUS),
  79.         'sen' => canGet(3, FOOT)
  80.     ),
  81.     'gos' => array(
  82.         'vas' => canGet(7, SUBWAY),
  83.         'sen' => canGet(3, SUBWAY),
  84.         'dvo' => canGet(6, FOOT),
  85.         'gor' => canGet(6, SUBWAY),
  86.         'let' => canGet(7, FOOT),
  87.         'vla' => canGet(7, FOOT)
  88.     ),
  89.     'sen' => array(
  90.         'ras' => canGet(3, FOOT),
  91.         'spo' => canGet(7, SUBWAY),
  92.         'gos' => canGet(3, SUBWAY),
  93.         'vla' => canGet(4, SUBWAY),
  94.         'vit' => canGet(2, SUBWAY),
  95.         'teh' => canGet(3, SUBWAY)
  96.     ),
  97.     'vla' => array(
  98.         'sen' => canGet(4, SUBWAY),
  99.         'gos' => canGet(7, FOOT),
  100.         'vit' => canGet(3, SUBWAY)
  101.     ),
  102.     'vit' => array(
  103.         'sen' => canGet(2, SUBWAY),
  104.         'teh' => canGet(2, SUBWAY),
  105.         'vla' => canGet(3, SUBWAY)
  106.     ),
  107.     'teh' => array(
  108.         'sen' => canGet(3, SUBWAY),
  109.         'vit' => canGet(2, SUBWAY)
  110.     )
  111. );
  112.  
  113. // Чтобы не писать много раз array('time' => ..., 'by' => ...), используем функцию. 
  114. $inf = 99999;
  115.  
  116. $start = 'pet';
  117. $end = 'nov';
  118. $path = [$end];
  119. $visited = [];
  120. $time = [];
  121.  
  122. foreach($paths as $graph => $value) {
  123.     $time[$graph] = $inf;
  124. }
  125. $time[$start] = 0;
  126.  
  127. function canGet($time, $byWhat) {
  128.     return array('time' => $time, 'by' => $byWhat);
  129. }
  130.  
  131. function findUnvisitedNodeWithLowestDistance($time, $visited) {
  132.     foreach($time as $t => $value) {
  133.         if(in_array($t, $visited)) {
  134.             unset($time[$t]);
  135.         }
  136.     }
  137.     return array_search(min($time), $time);
  138. }
  139. function Dijkstra($paths, $pos, $time, $visited, $start, $end, $path) {
  140.     $visited[] = $pos;
  141.     if(count($time) == count($visited)) {
  142.         return findShortestPath($paths, $time, $end, $path, $start);
  143.     }
  144.     foreach ($paths[$pos] as $g => $v) {
  145.         if ($time[$g] > $time[$pos] + $v['time']) {
  146.             $time[$g] = $time[$pos] + $v['time'];
  147.         }
  148.     }
  149.     $pos = findUnvisitedNodeWithLowestDistance($time, $visited);
  150.     return Dijkstra($paths, $pos, $time, $visited, $start, $end, $path);
  151. }
  152. function findShortestPath($paths, $time, $pos, $path, $start) { //Проблема в этом алгоритме
  153.     if($pos == $start) {
  154.         $path = array_reverse($path);
  155.         return $A = ['path' => $path, 'time' => $time];
  156.     }
  157.     foreach($paths[$pos] as $Graph => $value) {
  158.         if($time[$pos] == $time[$Graph] + $value['time']) {
  159.             $path[] = $Graph;
  160.             $pos = $Graph;
  161.             return findShortestPath($paths, $time, $pos, $path, $start);
  162.         }
  163.     }
  164. }
  165.  
  166. $A = Dijkstra($paths, $start, $time, $visited, $start, $end, $path);
  167. $path = $A['path'];
  168. $time = $A['time'];
  169.  
  170. echo "Начальная точка: ".$pointNames[$path[0]].". \n";
  171. for($i = 0; $i!=(count($path)-1);$i++) {
  172.     echo "Из нее ".$transportName[$paths[$path[$i]][$path[$i+1]]['by']]
  173.             ." до точки ".$pointNames[$path[$i+1]]
  174.             ." за ".$paths[$path[$i]][$path[$i+1]]['time']." мин.\n";
  175. }
  176. echo "В итоге ты попадаешь в точку ".$pointNames[$end]." за ".$time[$end]." минут.";
Success #stdin #stdout 0.02s 52472KB
comments (?)
stdin 
Standard input is empty
stdout 
Начальная точка: ст. м. Петроградская. 
Из нее едешь на метро до точки ст. м. Горьковская за 3 мин.
Из нее едешь на метро до точки Гостиный Двор за 6 мин.
Из нее едешь на метро до точки Сенная Площадь за 3 мин.
Из нее идешь пешком до точки Дом Раскольникова за 3 мин.
Из нее едешь на автобусе до точки Новая Голландия за 7 мин.
В итоге ты попадаешь в точку Новая Голландия за 22 минут.
https://ideone.com/KppkNl
language:
PHP (php 7.3.5)
created:
8 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!