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