Dijkstra算法 - 如何計算距離？

我從網站上的PHP類：http://www.giswiki.org/wiki/Algorithmus_von_Dijkstra 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 COORDS（GPS ...例如：56.292157，-88.022461）。我做了數學運算以獲得UTM中的相同座標（UTM給出數字X和Y，我得到了4142193,601021）。我得到了我的第一個和第二個值來填充我的數組。我不知道如何獲得第三個值的距離。

任何線索？

來源

2012-09-20 David Bélanger

您是否對算法如何計算從一個節點到每個其他節點的貪婪策略的距離感興趣？或者如何獲得結果（如您鏈接的示例中）？ – kmindi

看看陣列。假設我將這個條目寫成'array（2,10,30）' - 他如何得到30？因爲我想要做的是在PHP中創建一個路由腳本。 –

該數組表示兩個節點之間的預定義距離。這個距離不會改變。該算法將計算一個指定節點和其他每個可到達節點之間的距離（通過其他節點上的路由） – kmindi

應使用Great-circle_distance算法計算第三個值。那麼你可以使用dijkstra's algorithm。

來源

2012-09-20 21:56:34 kmindi

不錯。但是，這個算法需要2分。 2 X和2 Y.我不明白我怎麼可以用這個來找到距離使用一個點陣'（4142193，601021，??）' –

Dijkstra在任意圖上運行，你可以像你一樣定義重量或距離想。如果您有經度和緯度信息（例如來自OSM），那麼您可以計算每個節點的實際距離。我認爲，像4142193這樣的一個id直接映射到一個節點。所以例如你從OSM中導入你從id = 0開始的數據，然後用緯度填充另一個緯度數組（以及經度數組）。那麼你可以通過緯度[0]獲得節點0等的緯度，並獲得所需的緯度，兩個ID的距離來計算真實的距離 – Karussell

前兩個數字不是座標 - 它們是索引。因此，您需要爲每個點提供一個可用於引用該點的唯一索引。

array(0, 1, 4)指0點和1點之間的距離爲4。距離單位可以是任何你想要的。

來源

2012-09-20 22:18:34 fgb

我想你可能會對這個問題感到困惑。 Djistrka的算法在一個圖上運行，無論是有向還是無向。我不確定所給出的圖表是否應該被定向。（如果它是無向的，那麼數組（n1，n2，d）也意味着數組（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-20 23:21:36

現在我明白了，謝謝。所以現在我知道有2點（不是x和y）以及它們之間的距離。現在對我來說非常清楚。最後一個問題，我是否需要計算所有點之間的距離？假設我在城市周圍有3000個節點。我需要計算北部和南部最好的一個和每個例子之間的距離嗎？ –

運行Djikstra算法時，最終計算出單個節點和圖上所有節點之間的最短路徑。但是這並沒有給你所有節點之間的最短路徑。你可以爲每個節點重新運行Djikstra的算法，但是有更多的方法可以做到這一點（Floyd-Warshall算法） –

Dijkstra算法 - 如何計算距離？

回答

相關問題