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

Question

我想计算2个节点之间的最短路径。每个节点的位置类似于 [1,2]。当我使用 BFS 遍历节点时，我将每个节点标记为已访问并添加与起始节点的距离。当找到结束节点时，我想调用一个函数，传递开始和结束节点并获得最短路径

输入：

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

期望的输出：

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

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

Answer 1

如果我没理解错的话，你问的是如何从找到目标的 breadth-first 搜索中重建最短路径。

有几种方法可以做到这一点，但一种方法是将您的 visited-marking 变成一个标记，并向后引用您来自的节点。

在 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)

尽管您可以为“已访问”（或“已发现”）保留一个单独的布尔标志，但您可以仅使用此 parent 属性来保存 space：如果它是 non-null，认为该节点已访问。

找到目标节点后，您可以通过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 的实际数据结构，您可能需要反转它。

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

How to get shortest path between nodes on a grid?

javascript

algorithm

breadth-first-search