Кратчайший путь с помощью PHP

Question

У меня есть массив координат в PHP, как это:

Array ( 
    [0] => Array ( 
     [0] => 39.1057579 
     [1] => 26.5451331 
    ) 
    [1] => Array ( 
     [0] => 39.1057579 
     [1] => 26.5451331 
     [2] => 39.1055889 
     [3] => 26.5452403 
    ) 
    [2] => Array ( 
     [0] => 39.1057579 
     [1] => 26.5451331 
     [2] => 39.1055889 
    ) 
) 

Я собираюсь найти функцию с началом LatLng и конец LatLng в качестве входных данных и возвращает массив координат в кратчайшем дорожка.

Answer 1

Как указал Марк Бейкер, вам нужно использовать что-то вроде алгоритма Дейкстры для перемещения взвешенного графика (именно это вы будете иметь, когда будете включать расстояния).

Вот простая функция расстояния я нашел here:

<?php 

/*::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::*/ 
/*::                   :*/ 
/*:: This routine calculates the distance between two points (given the  :*/ 
/*:: latitude/longitude of those points). It is being used to calculate  :*/ 
/*:: the distance between two locations using GeoDataSource(TM) Products :*/ 
/*::                   :*/ 
/*:: Definitions:               :*/ 
/*:: South latitudes are negative, east longitudes are positive   :*/ 
/*::                   :*/ 
/*:: Passed to function:             :*/ 
/*:: lat1, lon1 = Latitude and Longitude of point 1 (in decimal degrees) :*/ 
/*:: lat2, lon2 = Latitude and Longitude of point 2 (in decimal degrees) :*/ 
/*:: unit = the unit you desire for results        :*/ 
/*::   where: 'M' is statute miles         :*/ 
/*::     'K' is kilometers (default)       :*/ 
/*::     'N' is nautical miles         :*/ 
/*:: Worldwide cities and other features databases with latitude longitude :*/ 
/*:: are available at http://www.geodatasource.com       :*/ 
/*::                   :*/ 
/*:: For enquiries, please contact sales@geodatasource.com     :*/ 
/*::                   :*/ 
/*:: Official Web site: http://www.geodatasource.com      :*/ 
/*::                   :*/ 
/*::   GeoDataSource.com (C) All Rights Reserved 2013     :*/ 
/*::                   :*/ 
/*::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::*/ 
function distance($lat1, $lon1, $lat2, $lon2, $unit) { 

    $theta = $lon1 - $lon2; 
    $dist = sin(deg2rad($lat1)) * sin(deg2rad($lat2)) + cos(deg2rad($lat1)) * cos(deg2rad($lat2)) * cos(deg2rad($theta)); 
    $dist = acos($dist); 
    $dist = rad2deg($dist); 
    $miles = $dist * 60 * 1.1515; 
    $unit = strtoupper($unit); 

    if ($unit == "K") { 
    return ($miles * 1.609344); 
    } else if ($unit == "N") { 
     return ($miles * 0.8684); 
    } else { 
     return $miles; 
     } 
} 

echo distance(32.9697, -96.80322, 29.46786, -98.53506, "M") . " Miles<br>"; 
echo distance(32.9697, -96.80322, 29.46786, -98.53506, "K") . " Kilometers<br>"; 
echo distance(32.9697, -96.80322, 29.46786, -98.53506, "N") . " Nautical Miles<br>"; 

?> 

Чтобы найти все расстояния между узлами, вам нужно просто перебрать все ваши узлы. Придешь с массивом, который выглядит примерно так:

$distance[0][1] = 10; 
$distance[0][2] = 12; 
$distance[0][3] = 7; 
... 
$distance[4][3] = 14; 

Где размеры вашего массива представляют свои номера узлов и присвоенное значение является расстоянием. Вы можете запустить этот массив через Dijkstra, чтобы найти кратчайший взвешенный путь.

Надеюсь, это вам поможет. Если вам нужна дополнительная помощь, вы можете попытаться уточнить свой вопрос, чтобы быть более узким. График обхода - ОЧЕНЬ широкая область изучения. Удачи.