fork download
copy 
  1. <?php // вычисление кратчайшего маршрута алгоритмом Дейкстры
  2.  
  3.  
  4. error_reporting(-1);
  5. define('SUBWAY', 'sub');
  6. define('FOOT', 'foot');
  7. define('BUS', 'bus');
  8.  
  9. $transportName = array(
  10.     SUBWAY  =>  'едешь на метро',
  11.     FOOT    =>  'идешь пешком',
  12.     BUS     =>  'едешь на автобусе'
  13. );
  14.  
  15.  
  16.  
  17. $startPoint = 'pet'; // начало маршрута
  18. $endPoint = 'teh'; // конец маршрута
  19. $infinity = 1000000; //вес маршрута соответствующий бесконечности
  20.  
  21.  
  22. $pointNames = array(
  23.     'pet'   =>  'ст. м. Петроградская',
  24.     'chk'   =>  'ст. м. Чкаловская',
  25.     'gor'   =>  'ст. м. Горьковская',
  26.     'spo'   =>  'ст. м. Спортивная',
  27.     'vas'   =>  'ст. м. Василеостровская',
  28.     'kre'   =>  'Петропавловская крепость',
  29.     'let'   =>  'Летний сад',
  30.     'dvo'   =>  'Дворцовая площадь',
  31.     'isa'   =>  'Исакиевский собор',
  32.     'nov'   =>  'Новая Голландия',
  33.     'ras'   =>  'Дом Раскольникова',
  34.     'gos'   =>  'Гостиный Двор',
  35.     'sen'   =>  'Сенная Площадь',
  36.     'vla'   =>  'ст. м. Владимирская',
  37.     'vit'   =>  'Витебский вокзал',
  38.     'teh'   =>  'Технологический Институт'
  39. );
  40.  
  41. $paths = array(
  42.     'pet'   =>  array(
  43.         'chk'   =>  canGet(10, BUS),
  44.         'gor'   =>  canGet(3, SUBWAY)
  45.     ),
  46.  
  47.     'chk'   =>  array(
  48.         'pet'   =>  canGet(10, BUS),
  49.         'spo'   =>  canGet(3, SUBWAY)
  50.     ),
  51.  
  52.     'gor'   =>  array(
  53.         'pet'   =>  canGet(3, BUS),
  54.         'kre'   =>  canGet(5, FOOT),
  55.         'gos'   =>  canGet(6, SUBWAY)
  56.     ),
  57.  
  58.     'spo'   =>  array(
  59.         'chk'   =>  canGet(3, SUBWAY),
  60.         'vas'   =>  canGet(10, BUS),
  61.         'sen'   =>  canGet(7, SUBWAY)
  62.     ),
  63.  
  64.     'vas'   =>  array(
  65.         'spo'   =>  canGet(10, BUS),
  66.         'gos'   =>  canGet(7, SUBWAY),
  67.         'nov'   =>  canGet(11, FOOT)
  68.     ),
  69.  
  70.     'kre'   =>  array(
  71.         'gor'   =>  canGet(5, FOOT)
  72.     ),
  73.  
  74.     'let'   =>  array(
  75.         'dvo'   =>  canGet(6, FOOT),
  76.         'gos'   =>  canGet(7, FOOT)
  77.     ),
  78.  
  79.     'dvo'   =>  array(
  80.         'isa'   =>  canGet(6, FOOT),
  81.         'gos'   =>  canGet(6, FOOT),
  82.         'let'   =>  canGet(6, FOOT)
  83.     ),
  84.  
  85.     'isa'   =>  array(
  86.         'dvo'   =>  canGet(6, FOOT),
  87.         'nov'   =>  canGet(5, FOOT)
  88.     ),
  89.  
  90.     'nov'   =>  array(
  91.         'vas'   =>  canGet(11, FOOT),
  92.         'isa'   =>  canGet(5, FOOT),
  93.         'ras'   =>  canGet(7, BUS)
  94.     ),
  95.  
  96.     'ras'   =>  array(
  97.         'nov'   =>  canGet(7, BUS),
  98.         'sen'   =>  canGet(3, FOOT)
  99.     ),
  100.  
  101.     'gos'   =>  array(
  102.         'vas'   =>  canGet(7, SUBWAY),
  103.         'sen'   =>  canGet(3, SUBWAY),
  104.         'dvo'   =>  canGet(6, FOOT),
  105.         'gor'   =>  canGet(6, SUBWAY),
  106.         'let'   =>  canGet(7, FOOT),
  107.         'vla'   =>  canGet(7, FOOT)        
  108.     ),
  109.  
  110.     'sen'   =>  array(
  111.         'ras'   =>  canGet(3, FOOT),
  112.         'spo'   =>  canGet(7, SUBWAY),
  113.         'gos'   =>  canGet(3, SUBWAY),
  114.         'vla'   =>  canGet(4, SUBWAY),
  115.         'vit'   =>  canGet(2, SUBWAY),
  116.         'teh'   =>  canGet(3, SUBWAY)
  117.     ),
  118.  
  119.     'vla'   =>  array(
  120.         'sen'   =>  canGet(4, SUBWAY),
  121.         'gos'   =>  canGet(7, FOOT),
  122.         'vit'   =>  canGet(3, SUBWAY)
  123.     ),
  124.  
  125.     'vit'   =>  array(
  126.         'sen'   =>  canGet(2, SUBWAY),
  127.         'teh'   =>  canGet(2, SUBWAY),
  128.         'vla'   =>  canGet(3, SUBWAY)
  129.     ),
  130.  
  131.     'teh'   =>  array(
  132.         'sen'   =>  canGet(3, SUBWAY),
  133.         'vit'   =>  canGet(2, SUBWAY)        
  134.     )
  135. );
  136.  
  137. /* Чтобы не писать много раз array('time' => ..., 'by' => ...), используем функцию. 
  138.     «canGet» переводится как «можно попасть» */
  139. function canGet($time, $byWhat) {
  140.     return array('time'     =>  $time, 'by' =>  $byWhat);
  141. }
  142.  
  143. function initialTime($pointName,$paths,$pointNames,$infinity){	//задаём время маршрутов, от выбраной точки до остальных, равным бесконечности
  144. 	foreach($pointNames as $name=>$nameLong){					//время движения от точки до неё самой равно 0
  145. 		if (array_key_exists($name,$paths[$pointName])){
  146. 			$pathArray[$name] = array('totalTime'=>$paths[$pointName][$name]['time'],'listOfRouts'=>array(1=>array($name,$paths[$pointName][$name]['time'],$paths[$pointName][$name]['by'])));	
  147. 		}
  148. 		elseif($name == $pointName){
  149. 			$pathArray[$name] = array('totalTime'=>0,'listOfRouts'=>array(1=>array($name,0,'Ты уже здесь.')));	
  150. 		}
  151. 		else{
  152. 			$pathArray[$name] = array('totalTime'=>$infinity,'listOfRouts'=>array());		
  153. 		}
  154. 	}
  155. 	return $pathArray;
  156. }
  157. function findLocalPointsTime($routs,$paths,$pointName){ 	//ищем время маршрутов от точки до её соседей
  158. 	$pathArrayInPoint = $routs;
  159. 	$pointContacts = $paths[$pointName];
  160. 	$pointTime = $routs[$pointName]['totalTime'];
  161. 	foreach($pointContacts as $name=>$routStat){
  162. 		$newTime = $pointTime + $routStat['time'];
  163. 		$oldTime = $routs[$name]['totalTime'];
  164. 		if($newTime<$oldTime){
  165. 			$pathArrayInPoint[$name]['totalTime'] = $newTime;
  166. 			$pathArrayInPoint[$name]['listOfRouts'] = $pathArrayInPoint[$pointName]['listOfRouts'];  
  167. 			$pathArrayInPoint[$name]['listOfRouts'][] = array($name,$routStat['time'],$routStat['by']); 
  168. 		}
  169. 	}
  170. 	return $pathArrayInPoint;
  171. }
  172.  
  173. function printRout($startPoint,$fastRout,$pointNames){		//вывод информации о маршруте
  174. 	$start = $startPoint;
  175. 	foreach($fastRout as $i=>$routStat){
  176. 		switch ($routStat[2]){
  177. 			case "sub":
  178. 				$byWith = "на метро";
  179. 				break;
  180. 			case "foot":
  181. 				$byWith = "пешком";
  182. 				break;
  183. 			case "bus":		
  184. 				$byWith = "на автобусе";
  185. 				break;
  186. 		}
  187. 		$end = $routStat[0];
  188. 		echo "От $pointNames[$start] до $pointNames[$end] $routStat[1] мин. $byWith\n";
  189. 		$start = $end;
  190. 	}
  191. }
  192.  
  193. //выбираем начальную точку
  194. //задаём время движения до всех остальных точек бесконечным
  195. //обходим все соседние точки и считаем время движения до них
  196. //от каждой соседней точки обходим их соседние точки и считаем обзее время движения до них из первой точки
  197.  
  198. $listOfPoints = array($startPoint);
  199. $listOfPoints2 = array();
  200. $listOfCheckedPoint = array();
  201.  
  202. $routs = initialTime($startPoint,$paths,$pointNames,$infinity);
  203. $n = 0;
  204. while (isset($listOfPoints2)&&$n<10){
  205. 	foreach($listOfPoints as $i=>$name){
  206. 		if (!in_array($name,$listOfCheckedPoint)){
  207. 			$routs = findLocalPointsTime($routs,$paths,$name);	
  208. 			$listOfCheckedPoint[] = $name;
  209. 			$b = $paths[$name];
  210. 			foreach($b as $name2=>$longName){
  211. 				$listOfPoints2[] = $name2;
  212. 			}
  213. 		}
  214. 	}	
  215. 	$listOfPoints = $listOfPoints2;
  216. 	$listOfPoints2 = array();
  217. 	$n++;
  218. }
  219. echo "Путь от $pointNames[$startPoint] до $pointNames[$endPoint] займёт {$routs[$endPoint]['totalTime']} мин.\n";
  220. echo "Маршрут:\n";
  221. printRout($startPoint,$routs[$endPoint]['listOfRouts'],$pointNames);
  222. echo "Приятной поездки!\n";
  223.  
  224.  
  225.  
  226.  
  227.  
Success #stdin #stdout 0.03s 52480KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Путь от ст. м. Петроградская до Технологический Институт займёт 15 мин.
Маршрут:
От ст. м. Петроградская до ст. м. Горьковская 3 мин. на метро
От ст. м. Горьковская до Гостиный Двор 6 мин. на метро
От Гостиный Двор до Сенная Площадь 3 мин. на метро
От Сенная Площадь до Технологический Институт 3 мин. на метро
Приятной поездки!
https://ideone.com/CcWLo1
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!