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 を得ました)。配列に入力するための最初と 2 番目の値を取得しました。3 番目の値の距離を取得する方法がわかりません。

手がかりはありますか？

4

3 に答える 3

3

3 番目の値は、Great-circle_distanceアルゴリズムを使用して計算する必要があります。次に、ダイクストラのアルゴリズムを使用できます。

于 2012-09-20T21:56:34.813 に答える
1

最初の 2 つの数値は座標ではなく、インデックスです。そのため、ポイントを参照するために使用できる一意のインデックスを各ポイントに付与する必要があります。

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 の 2 つのノードに接続されています。ノード 1 はノード 2 とノード 3 の 3 つのノードに接続されています。ノード 3 はノード 4 の 1 つのノードだけに接続されています。

次の問題に関心があるかもしれません: ノード 0 から始めて、ノード 4 に到達するにはどうすればよいでしょうか? 1 つのルートは、ノード 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 に答える