javascript - 如何获得网格上节点之间的最短路径？

Question

我想计算两个节点之间的最短路径。每个节点都有类似 [1,2] 的位置。当我使用 BFS 迭代节点时，我将每个节点标记为已访问并添加与起始节点的距离。当找到结束节点时，我想调用一个函数，通过开始和结束节点并获得最短路径
输入:

[3,3], [5,6], [all visited] (output included in all visited)

所需的输出:

[[3,4], [3,5], [3,6], [4,6]]

如何过滤所有访问过的路径以获得最短路径？

Answer 1

如果我理解正确，您会问如何从找到目标的广度优先搜索中重建最短路径。
有几种方法可以做到这一点，但一种是将您的访问标记转换为带有对您来自的节点的反向引用的标记。
在 Wikipedia您可以找到伪代码，其中该反向引用是 parent节点属性:

procedure BFS(G, root) is
     let Q be a queue
     label root as discovered
     Q.enqueue(root)
     while Q is not empty do
         v := Q.dequeue()
         if v is the goal then
             return v
         for all edges from v to w in G.adjacentEdges(v) do
             if w is not labeled as discovered then
                 label w as discovered
                 w.parent := v
                 Q.enqueue(w) 

尽管您可以为“已访问”(或“已发现”)保留一个单独的 bool 标志，但只需使用此 parent 就可以节省空间。属性:如果它不为空，则认为该节点已被访问。
找到目标节点后，您可以通过 parent 向后走back-reference 属性，直到到达起始节点。像这样往回走，修路并不难:

     if v is the goal then
         let path be a stack
         path.push(v)
         while v is not the root do
             v := v.parent
             path.push(v)
         return path

请注意，取决于 path 使用的实际数据结构您可能需要反转它。