How to get shortest path between nodes on a grid?

user_12826391 0
Viewed 219

I want to calculate the shortest path between 2 nodes. Each node has position like [1,2]. When i iterate over nodes using BFS i mark each node as visited and add distance from start node. When end node is found I want to call a function, pass start and end node and get shortest path

input:

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

desired output:

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

How do i filter all visited to get the shortest path?

breadth-first-search algorithm javascript
1 Answers

If I understand correctly, you are asking how you can reconstruct the shortest path from a breadth-first search that found a target.

There are several ways to do this, but one is to turn your visited-marking into a marking with a back reference to the node you came from.

On Wikipedia you can find pseudo code where this back reference is a parent property of the node:

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)

Although you can keep a separate, boolean flag for "visited" (or "discovered"), you can save space by just using this parent property: if it is non-null, consider the node as visited.

Once you have found the target node, you can walk backwards via the parent back-reference property until you arrive at the starting node. It is not difficult to build the path while you walk back like that:

     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

Note that depending of the actual data structure used for path you may need to reverse it.

user_54598390
Related