Dijkstra在三維陣列上的算法

我真的不知道如何在僞代碼中實現這一點。用戶在像這樣進入：Dijkstra在三維陣列上的算法

[ 
    [ 
    [0,1] 
    ], 
    [ 
    [5,6],[7,8] 
    ], 
    [ 
    [91,17],[18,42] 
    ], 
    [ 
    [20,54] 
    ] 
]

基本上這是在[0,1]映射到（和[5,6] [7,8]），其中每個映射到（[91的路徑， 17]和[18,42]）等等，成本是點之間的距離。起點爲[0，1]，終點爲[20,54]。始終有一個起點和一個終點，並且前一個索引中的所有點都映射到下一個索引中的點。

如何爲這種數據結構實現Dijkstra算法？

該圖像可以幫助（不按比例）： enter image description here

綠色的是起點和紅色是結束。

來源

2015-04-01 KthProg

我讀三次，但我仍然不知道數組的意思之間。它是路徑嗎？ – 2015-04-01 13:51:35

@ThomWiggers我在這裏提出了一個更好的解釋。是的，它是路徑，成本就是距離。 – KthProg 2015-04-01 13:53:33

@KthProg不，你沒有;-) – Alnitak 2015-04-01 13:54:01

請注意，如果我們將數組中的條目視爲一對(x, y)，給定的數組是二維的。

基本思想是構建圖，分配邊的成本，然後應用標準的Dijkstra算法。

構建圖：

製作2個哈希表H和Q其中H([x,y])頂點(x,y)映射到0和n - 1之間的數，和Q0和n - 1之間的整數映射到頂點(x, y)。 n是圖中頂點的數量。通過遍歷給定的2d數組中的所有頂點，我們可以輕鬆找到n。讓我們把給定數組散列的A

僞代碼：

n = 0 
for(i = 0; i < length of A ; i++) 
    for(int j = 0; j < length of A[i]; j++) 
      H[A[i][j]] = n 
      Q[n] = A[i][j] 
      n++

注意A[i][j]實際上是一對整數，所以H的關鍵應該是一對整數。

現在我們可以構建考慮頂點的圖形作爲0和n - 1之間的數字。我們可以代表中的圖形構造圖的adjacency list

Psudo代碼：

array g[n][]        //-- adjacency list of the graph 
for(int i = 0; i < length of A - 1; i++) //-- notice the "-1" 
    for(int j = 0; j < length of A[i]; j++) 
     for(int k = 0; k < length of A[i + 1]; k++) 
      g[ H[A[i][j]] ].insert (H[ A[i + 1][k] ]) 
      g[ H[ A[i + 1][k] ].insert(H[A[i][j]])  //-- assuming the graph is undirected

通過這樣做，我們已經建立了圖表。現在我們可以在圖形g上應用標準Dijkstra算法。爲了找到兩個頂點u和v之間的邊的代價，我們可以使用散列表Q以獲得u和v的座標。那麼邊緣的成本是Q[u]和Q[v]之間的Euclidean distance。

一條邊的成本僞碼兩個頂點u和v

cost(int u, int v) 
    return Euclidean_distance(Q[u], Q[v])

來源

2015-04-01 17:12:20 MrGreen

Dijkstra在三維陣列上的算法

回答

相關問題