0

我从网站上得到了 PHP 类：http: //www.giswiki.org/wiki/Algorithmus_von_Dijkstra

在我看到的代码中：

// $points is an array in the following format: (router1,router2,distance-between-them)
$points = array(
    array(0,1,4),
    array(0,2,I),
    array(1,2,5),
    array(1,3,5),
    array(2,3,5),
    array(3,4,5),
    array(4,5,5),
    array(4,5,5),
    array(2,10,30),
    array(2,11,40),
    array(5,19,20),
    array(10,11,20),
    array(12,13,20),
);

得到“他们之间的距离”的数学是什么？我无法弄清楚这背后的数学原理。

我有 WSG84 坐标（GPS ......例如：56.292157，-88.022461）。我进行了数学运算以在 UTM 中获得相同的坐标（UTM 给出数字 X 和 Y，我得到 4142193、601021）。我得到了第一个和第二个值来填充我的数组。我不知道如何获得第三个值的距离。

有什么线索吗？

4

3 回答 3

3

第三个值应使用Great-circle_distance算法计算。然后你可以使用dijkstra的算法。

于 2012-09-20T21:56:34.813 回答
1

前两个数字不是坐标——它们是索引。因此，您需要为每个点提供一个唯一索引，该索引可用于引用该点。

array(0, 1, 4)表示点 0 和点 1 之间的距离为 4。距离的单位可以是任何你想要的。

于 2012-09-20T22:18:34.293 回答
0

我想你可能对这个问题有点困惑。Djistrka 的算法在有向或无向图上运行。我不确定给出的图表是否应该是定向的。（如果它是无向的，那么 array(n1, n2, d) 也意味着 array(n2, n1, d)

图形不必具有物理 x,y 坐标。您可以简单地拥有一个顶点或节点列表以及它们之间的距离。

给出的数据结构可能不是可视化问题的最佳方式。更好的方法可能如下：

$points = array(
array(0, array(1, 4). arrau(2. 1)),
array(1, array(2, 5). array(3. 5)),
array(2, array(3,5), array(10, 30), array(11, 30),
array(3, array(4,5)),
array(4, array(5,5)),
array(5, array(19,20)),
array(10, array(11,20)),
array(12, array(13,20)))

在伪代码中，这表示

Node 0 -> Node 1 (distance 4), Node 2 (distance 1)
Node 1 -> Node 2 (distance 1), Node 3 (distance 5)
etc.

假设这是定向的，这稍微简化了问题，这个数组现在表示所有节点的连接性。例如，节点 0 连接到两个节点，节点 1 和节点 2。节点 1 连接到 3 个节点，节点 2 和节点 3。节点 3 仅连接到一个节点，节点 4。

我们可能对以下问题感兴趣：从节点 0 开始，我们如何到达节点 4？一种路线是节点 0 到节点 1（距离 4）到节点 3（距离 5）到节点 4（距离 5）。总行驶距离为 4 + 5 + 5 = 14。

现在我们问一个问题：那是最短的路线吗？由于该图是如此之小并且连接得不是很好，在这种情况下您可以看到它。到达节点 4 的唯一方法是来自节点 3，到达节点 3 的唯一方法是来自节点 2 或节点 1。要到达节点 2，我们可以来自节点 0 或节点 1。但是通过节点 1 只会使行程更长，因此很明显解决方案是节点 0 -> 节点 2 -> 节点 3 -> 节点 4。

希望澄清有所帮助。

于 2012-09-20T23:21:36.400 回答