-5

我在 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 作为输入的函数，并返回一个坐标数组作为最短路径。

4

1 回答 1

1

正如 Mark Ba​​ker 指出的那样，您需要使用 Dijkstra 算法之类的东西来遍历加权图（这就是您在包含距离时所拥有的）。

这是我在这里找到的一个简单的距离函数：

<?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 运行此数组以找到最短的加权路径。

希望这对您有所帮助。如果您需要进一步的帮助，您可能想尝试将您的问题细化为更窄。图遍历是一个非常广泛的研究领域。祝你好运。

于 2013-10-01T23:46:03.787 回答