三维数组上的 Dijkstra 算法

Question

我真的不知道如何在伪代码中实现它。用户输入如下内容：

[
  [
     [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 算法？

这张图片可能有帮助（不按比例）：

绿色是起点，红色是终点。

Answer 1

请注意，如果我们将数组中的条目视为一对 (x, y)。

，则给定数组是二维的

基本思路是构建图，分配边的成本，然后应用标准 Dijkstra 算法。

构建图表：

制作 2 个散列 tables H 和 Q 其中 H([x,y]) 将顶点 (x,y) 映射到 0 和 n - 1，Q 将 0 和 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的key应该是一对整数。

现在我们可以构建图，将顶点视为 0 和 n - 1 之间的数字。我们可以将图形表示为 adjacency list

构建图的伪代码：

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 之间边的成本，我们可以使用散列 table Q 以获得 u 和 v。那么边的成本就是点 Q[u] 和 Q[v].

之间的 Euclidean distance

两个顶点 u 和 v 之间的边成本的伪代码

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

三维数组上的 Dijkstra 算法

Dijkstra's algorithm on three dimensional array

javascript

arrays

algorithm

dijkstra

multidimensional-array