javascript - 三维阵列的Dijkstra算法

即使在psuedo代码中，我也不知道如何实现这一点。用户输入如下内容：

[
  [
     [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算法？
此图像可能有帮助（不可缩放）：
绿色是开始，红色是结束。

最佳答案

注意，如果我们将数组中的条目视为一对(x, y)，那么给定的数组是二维的。
基本思想是建立图，分配边的代价，然后应用标准dijkstra算法。
构建图表：
制作两个散列表H和Q，其中H([x,y])将一个顶点(x,y)映射到0和n - 1之间的数字，Q将0和n - 1之间的整数映射到一个顶点(x, y)。n是图形中的顶点数。通过在给定的n数组中的所有顶点上循环，我们可以很容易地找到2d让我们调用给定的数组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

通过这样做，我们已经建立了图表现在我们可以在图上应用标准dijkstra算法。为了找出两个顶点之间的边的代价，我们可以使用hash表来获得g和u的坐标。那么边缘的代价是点v和点Q之间的Euclidean distance。
两个顶点之间边的代价的伪代码u和v

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

关于javascript - 三维阵列的Dijkstra算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/29392586/