使用PHP的最短路径 [英] Shortest path using php

问题描述

我在php中有一个这样的坐标数组：

i have an array of coordinates in php like this:

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
    )
)

我要找到一个以start latlng和end latlng为输入的函数，并返回一个坐标数组作为最短路径

I'm going to find a function with start latlng and end latlng as inputs and return an array of coordinates as the shortest path.

推荐答案

正如Mark Ba​​ker所指出的，您需要使用Dijkstra算法之类的方法来遍历加权图（

As Mark Baker pointed out, you'll need to use something like Dijkstra's algorithm to traverse a weighted graph (which is what you'll have when you include distances).

这是我发现的一个简单的距离函数此处：

Here's a simple distance function I found 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 [e-mail]                  :*/
/*::                                                                         :*/
/*::  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>";

?>

要查找节点之间的所有距离，您只需简单地遍历所有节点。您将得到一个看起来像这样的数组：

To find all distances between nodes, you'll need to simply loop through all your nodes. You'll come out with an array that looks something like this:

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

其中数组的维数表示节点号，分配的值是距离。您可以通过Dijkstra运行该数组以找到最短的加权路径。

Where the dimensions of your array represent your node numbers, and the assigned value is the distance. You'd run this array through Dijkstra to find the shortest weighted path.

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

Hope this helps you. If you need further assistance you might want to try to refine your question to be more narrow. Graph traversal is a VERY broad area of study. Good luck.

这篇关于使用PHP的最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！