javascript - 三维数组上的 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 个哈希表 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 之间边的成本，我们可以使用哈希表 Q 以获得 的坐标>u 和 v。那么边缘的成本是Euclidean distance在点 Q[u] 和 Q[v] 之间。

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

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