fork(2) download 
  1. <?php
  2.  
  3. $paths = array(
  4.     'pet'   =>  array(
  5.     		'visited' 		=>  false,
  6.     		'shortest_path' =>  INF,
  7.     		'from' 		    =>  '',
  8.     		'neighbors'     =>  array(
  9.         		'chk'   =>  array('time'      => 10,
  10.         						  'transport' => 'bus'),
  11.         		'gor'   =>  array('time'      => 3,
  12.         						  'transport' => 'sub'),
  13.     	)
  14.     ),
  15.  
  16.     'chk'   =>  array(
  17.     		'visited' 		=>  false,
  18.     		'shortest_path' =>  INF,
  19.     		'from' 		    =>  '',
  20.     		'neighbors'     =>  array(
  21.         		'pet'   =>  array('time'      => 10,
  22.         						  'transport' => 'bus'),
  23.         		'spo'   =>  array('time'      => 3,
  24.         						  'transport' => 'sub'),
  25.     	)
  26.     ),
  27.  
  28.     'gor'   =>  array(
  29.     		'visited' 		=>  false,
  30.     		'shortest_path' =>  INF,
  31.     		'from' 		    =>  '',
  32.     		'neighbors'     =>  array(
  33.         		'pet'   =>  array('time'      => 3,
  34.         						  'transport' => 'bus'),
  35.         		'kre'   =>  array('time'      => 5,
  36.         						  'transport' => 'foot'),
  37.         		'gos'   =>  array('time'      => 6,
  38.         						  'transport' => 'sub'),
  39.     	)
  40.     ),
  41.  
  42.     'spo'   =>  array(
  43.     		'visited' 		=>  false,
  44.     		'shortest_path' =>  INF,
  45.     		'from' 		    =>  '',
  46.     		'neighbors'     =>  array(
  47.         		'chk'   =>  array('time'      => 3,
  48.         						  'transport' => 'sub'),
  49.         		'vas'   =>  array('time'      => 10,
  50.         						  'transport' => 'bus'),
  51.         		'sen'   =>  array('time'      => 7,
  52.         						  'transport' => 'sub'),
  53.     	)
  54.     ),
  55.  
  56.     'vas'   =>  array(
  57.     		'visited' 		=>  false,
  58.     		'shortest_path' =>  INF,
  59.     		'from' 		    =>  '',
  60.     		'neighbors'     =>  array(
  61.         		'spo'   =>  array('time'      => 10,
  62.         						  'transport' => 'bus'),
  63.         		'gos'   =>  array('time'      => 7,
  64.         						  'transport' => 'sub'),
  65.         		'nov'   =>  array('time'      => 11,
  66.         						  'transport' => 'foot'),
  67.     	)
  68.     ),
  69.  
  70.     'kre'   =>  array(
  71.     		'visited' 		=>  false,
  72.     		'shortest_path' =>  INF,
  73.     		'from' 		    =>  '',
  74.     		'neighbors'     =>  array(
  75.         		'gor'   =>  array('time'      => 5,
  76.         						  'transport' => 'foot'),
  77.     	)
  78.     ),
  79.  
  80.     'let'   =>  array(
  81.     		'visited' 		=>  false,
  82.     		'shortest_path' =>  INF,
  83.     		'from' 		    =>  '',
  84.     		'neighbors'     =>  array(
  85.         		'dvo'   =>  array('time'      => 6,
  86.         						  'transport' => 'foot'),
  87.         		'gos'   =>  array('time'      => 7,
  88.         						  'transport' => 'foot'),
  89.     	)
  90.     ),
  91.  
  92.     'dvo'   =>  array(
  93.     		'visited' 		=>  false,
  94.     		'shortest_path' =>  INF,
  95.     		'from' 		    =>  '',
  96.     		'neighbors'     =>  array(
  97.         		'isa'   =>  array('time'      => 6,
  98.         						  'transport' => 'foot'),
  99.         		'gos'   =>  array('time'      => 6,
  100.         						  'transport' => 'foot'),
  101.         		'let'   =>  array('time'      => 6,
  102.         						  'transport' => 'foot'),
  103.     	)
  104.     ),
  105.  
  106.     'isa'   =>  array(
  107.     		'visited' 		=>  false,
  108.     		'shortest_path' =>  INF,
  109.     		'from' 		    =>  '',
  110.     		'neighbors'     =>  array(
  111.         		'dvo'   =>  array('time'      => 6,
  112.         						  'transport' => 'foot'),
  113.         		'nov'   =>  array('time'      => 5,
  114.         						  'transport' => 'foot'),
  115.     	)
  116.     ),
  117.  
  118.     'nov'   =>  array(
  119.     		'visited' 		=>  false,
  120.     		'shortest_path' =>  INF,
  121.     		'from' 		    =>  '',
  122.     		'neighbors'     =>  array(
  123.         		'vas'   =>  array('time'      => 11,
  124.         						  'transport' => 'foot'),
  125.         		'isa'   =>  array('time'      => 5,
  126.         						  'transport' => 'foot'),
  127.         		'ras'   =>  array('time'      => 7,
  128.         						  'transport' => 'bus'),
  129.     	)
  130.     ),
  131.  
  132.     'ras'   =>  array(
  133.     		'visited' 		=>  false,
  134.     		'shortest_path' =>  INF,
  135.     		'from' 		    =>  '',
  136.     		'neighbors'     =>  array(
  137.         		'nov'   =>  array('time'      => 7,
  138.         						  'transport' => 'bus'),
  139.         		'sen'   =>  array('time'      => 3,
  140.         						  'transport' => 'foot'),
  141.     	)
  142.     ),
  143.  
  144.     'gos'   =>  array(
  145.     		'visited' 		=>  false,
  146.     		'shortest_path' =>  INF,
  147.     		'from' 		    =>  '',
  148.     		'neighbors'     =>  array(
  149.         		'vas'   =>  array('time'      => 7,
  150.         						  'transport' => 'sub'),
  151.         		'sen'   =>  array('time'      => 3,
  152.         						  'transport' => 'sub'),
  153.         		'dvo'   =>  array('time'      => 6,
  154.         						  'transport' => 'foot'),
  155.         		'gor'   =>  array('time'      => 6,
  156.         						  'transport' => 'sub'),
  157.         		'let'   =>  array('time'      => 7,
  158.         						  'transport' => 'foot'),
  159.         		'vla'   =>  array('time'      => 7,
  160.         						  'transport' => 'foot'),    
  161.     	)
  162.     ),
  163.  
  164.     'sen'   =>  array(
  165.     		'visited' 		=>  false,
  166.     		'shortest_path' =>  INF,
  167.     		'from' 		    =>  '',
  168.     		'neighbors'     =>  array(
  169.         		'ras'   =>  array('time'      => 3,
  170.         						  'transport' => 'foot'),
  171.         		'spo'   =>  array('time'      => 7,
  172.         						  'transport' => 'sub'),
  173.         		'gos'   =>  array('time'      => 3,
  174.         						  'transport' => 'sub'),
  175.         		'vla'   =>  array('time'      => 4,
  176.         						  'transport' => 'sub'),
  177.         		'vit'   =>  array('time'      => 2,
  178.         						  'transport' => 'sub'),
  179.         		'teh'   =>  array('time'      => 3,
  180.         						  'transport' => 'sub'),
  181.     	)
  182.     ),
  183.  
  184.     'vla'   =>  array(
  185.     		'visited' 		=>  false,
  186.     		'shortest_path' =>  INF,
  187.     		'from' 		    =>  '',
  188.     		'neighbors'     =>  array(
  189.         		'sen'   =>  array('time'      => 4,
  190.         						  'transport' => 'sub'),
  191.         		'gos'   =>  array('time'      => 7,
  192.         						  'transport' => 'foot'),
  193.         		'vit'   =>  array('time'      => 3,
  194.         						  'transport' => 'sub'),
  195.     	)
  196.     ),
  197.  
  198.     'vit'   =>  array(
  199.     		'visited' 		=>  false,
  200.     		'shortest_path' =>  INF,
  201.     		'from' 		    =>  '',
  202.     		'neighbors'     =>  array(
  203.         		'sen'   =>  array('time'      => 2,
  204.         						  'transport' => 'sub'),
  205.         		'teh'   =>  array('time'      => 2,
  206.         						  'transport' => 'sub'),
  207.         		'vla'   =>  array('time'      => 3,
  208.         						  'transport' => 'sub'),
  209.     	)
  210.     ),
  211.  
  212.     'teh'   =>  array(
  213.     		'visited' 		=>  false,
  214.     		'shortest_path' =>  INF,
  215.     		'from' 		    =>  '',
  216.     		'neighbors'     =>  array(
  217.         		'sen'   =>  array('time'      => 3,
  218.         						  'transport' => 'sub'),
  219.         		'vit'   =>  array('time'      => 2,
  220.         						  'transport' => 'sub'),  
  221.     	)
  222.     )
  223. );
  224.  
  225. $start_point = pet;
  226. $end_point = nov;
  227.  
  228.  
  229.  function asd($paths,$start_point,$end_point)
  230.  {	
  231.  	$constant_start_point = $start_point;
  232.  	$constant_end_point   = $end_point;
  233.  	$transportName = array(
  234. 				sub => 'Из неё едешь на метро',
  235. 				foot => 'Из неё идешь пешком',
  236. 				bus => 'Из неё едешь на автобусе'
  237. 	);
  238.  	$shortest_path = $paths[$start_point]['shortest_path'];
  239.  	$paths[$start_point]['shortest_path'] = 0; // делаем длинну пути стартовой точки = 0
  240.  	$paths[$start_point]['from'] = 'start';
  241.  	while ($paths[$end_point]['visited'] == false) { // циклим пока точка до которой мы идем не станет true
  242.  		$paths[$start_point]['visited'] = true; // ставим посещение true 
  243.  		foreach ($paths[$start_point]['neighbors'] as $name => $time_transport) { // смотрим соседей вершины и длинну пути и присваем if длина пути+пройденый путь меньше чем есть
  244. 			if ($paths[$name]['visited'] == false) {
  245. 				$time = $time_transport['time'];
  246. 				if ($time+$paths[$start_point]['shortest_path'] < $paths[$name]['shortest_path']) {
  247. 					$paths[$name]['shortest_path'] = $time+$paths[$start_point]['shortest_path'];
  248. 					$paths[$name]['from'] = $start_point;
  249. 				}
  250. 			} 
  251. 		}
  252. 		$j = INF;
  253. 		foreach ($paths as  $name => $value) { // делаем старт поинт вершину с наименьшем пути
  254. 			if ($paths[$name]['visited'] == false ) {
  255. 				if ($paths[$name]['shortest_path'] < $j) {
  256. 					$j = $paths[$name]['shortest_path'];
  257. 					$start_point = $name;
  258. 				}
  259. 			}
  260. 		}
  261.  	}
  262.     while ($paths[$end_point]['from'] != 'start') {  // циклим пока не дойдем до начальной точки
  263.     	$faster_paths[] = $end_point;
  264.     	$end_point = $paths[$end_point]['from'];
  265.     } 
  266.  	krsort($faster_paths); // сортируем что бы по порядку шёл
  267.  	echo "Начальная точка: $constant_start_point\n";
  268. 	foreach ($faster_paths as $path) {
  269. 		echo $transportName[$paths[$paths[$path]['from']]['neighbors'][$path]['transport']]." до точки ".$path." за ".$paths[$paths[$path]['from']]['neighbors'][$path]['time']." мин.\n";
  270. 	}
  271. 	echo "В итоге ты попадешь в точку $constant_end_point за ".$paths[$constant_end_point]['shortest_path']." минут.";
  272. }		
  273.  
  274.  
  275. asd($paths,$start_point,$end_point);
  276.  
  277.  
  278.  
  279.  
  280.  
  281.  
  282.  
  283.  
Success #stdin #stdout #stderr 0.01s 82880KB
comments (?)
stdin 
Standard input is empty
stdout 
Начальная точка: pet
Из неё едешь на метро до точки gor за 3 мин.
Из неё едешь на метро до точки gos за 6 мин.
Из неё едешь на метро до точки sen за 3 мин.
Из неё идешь пешком до точки ras за 3 мин.
Из неё едешь на автобусе до точки nov за 7 мин.
В итоге ты попадешь в точку nov за 22 минут.
stderr 
PHP Notice:  Use of undefined constant pet - assumed 'pet' in /home/6JVyqO/prog.php on line 225
PHP Notice:  Use of undefined constant nov - assumed 'nov' in /home/6JVyqO/prog.php on line 226
PHP Notice:  Use of undefined constant sub - assumed 'sub' in /home/6JVyqO/prog.php on line 234
PHP Notice:  Use of undefined constant foot - assumed 'foot' in /home/6JVyqO/prog.php on line 235
PHP Notice:  Use of undefined constant bus - assumed 'bus' in /home/6JVyqO/prog.php on line 236
https://ideone.com/FjiolC
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!