fork(1) download 
  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.  	foreach ($paths as $name => $value) { // Проверяем есть ли такие точки.
  213.  		if ($start_point == $name) {
  214.  			$check_start_point = true;
  215.  		}elseif ($end_point == $name) {
  216.  			$check_end_point = true;
  217.  		}
  218.  	}
  219.  	if ($check_start_point != true) {
  220.  		echo "Такой точки не существует ".$start_point;
  221.  		return;
  222.  	}elseif ($check_end_point != true) {
  223.  		echo "Такой точки не существует ".$end_point;
  224.  		return;
  225.  	}
  226.  
  227.  
  228.  
  229.  	$current_point = $start_point;
  230.  	$paths[$current_point]['shortest_path'] = 0; // делаем длинну пути стартовой точки = 0
  231.  	while ($paths[$end_point]['visited'] == false) { // циклим пока точка до которой мы идем не станет true
  232.  		$paths[$current_point]['visited'] = true; // ставим посещение true 
  233.  		foreach ($paths[$current_point]['neighbors'] as $name => $time_transport) { // смотрим соседей вершины и длинну пути и присваем if длина пути+пройденый путь меньше чем есть
  234. 			if ($paths[$name]['visited'] == false) {
  235. 				$time = $time_transport['time'];
  236. 				if ($time+$paths[$current_point]['shortest_path'] < $paths[$name]['shortest_path']) {
  237. 					$paths[$name]['shortest_path'] = $time+$paths[$current_point]['shortest_path'];
  238. 				}
  239. 			} 
  240. 		}
  241. 		$j = INF; // переменная для сравнения
  242. 		foreach ($paths as  $name => $value) { // делаем старт поинт вершину с наименьшем пути
  243. 			if ($paths[$name]['visited'] == false ) {
  244. 				if ($paths[$name]['shortest_path'] < $j) {
  245. 					$j = $paths[$name]['shortest_path'];
  246. 					$current_point = $name;
  247. 				}
  248. 			}
  249. 		}
  250.  	}
  251.  	print_shortest_path($paths, $start_point, $end_point);
  252. }		
  253.  
  254. function print_shortest_path($paths, $start_point, $end_point) // Печатаем путь
  255. {
  256. 	$transportName = array(
  257. 				'sub' => 'Из неё едешь на метро',
  258. 				'foot' => 'Из неё идешь пешком',
  259. 				'bus' => 'Из неё едешь на автобусе'
  260. 	);
  261. 	$j = INF;
  262. 	$curent_point = $end_point;
  263.     while ($paths[$curent_point]['shortest_path'] != 0) {  // циклим пока не дойдем до начальной точки
  264.     	$made_path[] = $curent_point;
  265.     	foreach ($paths[$curent_point]['neighbors'] as  $name => $time_transport) { 
  266. 			if ($paths[$name]['visited'] == true ) {
  267. 				if ($paths[$name]['shortest_path'] < $j) {
  268. 					$transport_name = $time_transport['transport'];
  269. 					$j = $paths[$name]['shortest_path'];
  270. 					$curent_point = $name;
  271. 				}
  272. 			}
  273. 		}
  274.     } 
  275.     $made_path[] = $start_point;
  276.     $made_path   = array_reverse ($made_path);
  277. 	echo "Начальная точка: $start_point\n";
  278. 	foreach ($made_path as $key => $path) {
  279. 		if ($path == 'pet') {
  280. 			continue;
  281. 		}
  282. 		echo $transportName[$paths[$made_path[$key-1]]['neighbors'][$path]['transport']]
  283. 		." до точки ".$path." за "
  284. 		.$paths[$made_path[$key-1]]['neighbors'][$path]['time']." мин.\n";
  285. 	}
  286. 	echo "В итоге ты попадешь в точку $end_point за ".$paths[$end_point]['shortest_path']." мин.\n";
  287. }
  288.  
  289. $start_point = 'pet';
  290. $end_point = 'nov';
  291.  
  292.  get_shortest_path($paths,$start_point, $end_point);
  293.  
  294.  
  295.  
  296.  
  297.  
  298.  
  299.  
  300.  
  301.  
Success #stdin #stdout 0s 82880KB
comments (?)
stdin 
Standard input is empty
stdout 
Начальная точка: pet
Из неё едешь на метро до точки gor за 3 мин.
Из неё едешь на метро до точки gos за 6 мин.
Из неё едешь на метро до точки sen за 3 мин.
Из неё идешь пешком до точки ras за 3 мин.
Из неё едешь на автобусе до точки nov за 7 мин.
В итоге ты попадешь в точку nov за 22 мин.
https://ideone.com/fDcUub
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!