Path Finding Algorithms

However, it is not necessary to examine all possible paths. Algorithms such as Greedy, Dijkstra’s algorithm, and A* eliminate paths either using educated guesses(heuristics) or distance from source to node V to find the optimal path. By eliminating impossible paths, these algorithms can achieve time complexities as low as O(E log(V)).

Breadth-First Search (BFD)

It starts at the root and explores all of it’s children in the next level(neighbors) before moving to each of the root children, and then, it explores the children of the root children, and so on. The algorithm uses a queue to perform the BFS.

1. Add root node to the queue, and mark it as visited(already explored).
2. Loop on the queue as long as it's not empty.
   1. Get and remove the node at the top of the queue(current).
   2. For every non-visited child of the current node, do the following: 
       1. Mark it as visited.
       2. Check if it's the goal node, If so, then return it.
       3. Otherwise, push it to the queue.
3. If queue is empty, then goal node was not found!

Depth-First Search (DFD)

It starts at the root and explores one of it’s children’s sub tree, and then move to the next child’s sub tree, and so on. It uses stack, or recursion to perform the DFS.

Recursive

1. Mark the current node as visited(initially current node is the root node)
2. Check if current node is the goal, If so, then return it.
3. Iterate over children nodes of current node, and do the following:
    1. Check if a child node is not visited.
    2. If so, then, mark it as visited.
    3. Go to it's sub tree recursively until you find the goal node(In other words, do the same steps here passing the child node as the current node in the next recursive call).
    4. If the child node has the goal node in this sub tree, then, return it.
3. If goal node is not found, then goal node is not in the tree!

Iterative

1. Add root node to the stack.
2. Loop on the stack as long as it's not empty.
    1. Get the node at the top of the stack(current), mark it as visited, and remove it.
    2. For every non-visited child of the current node, do the following:
        1. Check if it's the goal node, If so, then return this child node.
        2. Otherwise, push it to the stack.
3. If stack is empty, then goal node was not found!

Dijkstra

Dijkstra’s algorithm tries to find the shortest path from the starting(root) node to every node, hence we can get the shortest path from the starting node to the goal.

1. Assign dis[v] for all nodes = INT_MAX (distance from root node to every other node).
2. Assign dis[root] = 0(distance from root node to itself).
3. Add all nodes to a priority queue.
4. Loop on the queue as long as it's not empty.
   1. In every loop, choose the node with the minimum distance from the root node in the queue(root node will be selected first).
   2. Remove the current chosen node from the queue.
   3. If the current chosen node is the goal node, then return it.
   4. For every child of the current node, do the following:
       1. If child node is not already in the queue, then skip this iteration.
       2. Assign temp = dist[current] + distance from current to child node.
       3. If temp < dist[child], then, assign dist[child] = temp. This denotes a shorter path to child node has been found.
5. If queue is empty, then goal node was not found!

Greedy

Greedy is an algorithm which makes a choice based on educated guesses(heuristics) at each stage. The node with shortest heuristic distance from the goal node will be explored next.

Given the heuristic distance of A, B, C, D, E, & F to goal node equals to 8, 8, 6, 5, 1, & 4 respectively.

1. Assign dis[v] for all nodes = INT_MAX (distance from every node to goal node).
2. Assign dis[root] = heuristics(root, goal) (distance from root node to goal).
3. Add root node to priority queue.
4. Loop on the queue as long as it's not empty.
   1. In every loop, choose the node with the minimum heuristic distance from the goal node in the queue(root node will be selected first).
   2. Remove the current chosen node from the queue (vis[current] = true).
   3. If the current chosen node is the goal node, then return it.
   4. For every child of the current node, do the following:
       1. If child node is already visited (previously removed from the queue), then skip this iteration.
       2. Assign dist[current] = heuristics(current, goal).
       3. Add child node to the queue.
5. If queue is empty, then goal node was not found!

A*(A star)

A* is same as Dijkstra, but it uses distance from the root node plus heuristics distance to the goal. The algorithm terminates when we find the goal node (same as Greedy).

Given the same heuristic distances mentioned above.

1. Assign dis[v] for all nodes = INT_MAX (distance from root node + heuristics of every node).
2. Assign dis[root] = 0 + heuristic(root, goal) (distance from root node to itself + heuristics).
2. Add root node to priority queue.
3. Loop on the queue as long as it's not empty.
   1. In every loop, choose the node with the minimum distance from the root node in the queue + heuristic (root node will be selected first).
   2. Remove the current chosen node from the queue (vis[current] = true).   
   3. If the current node is the goal node, then return it.
   4. For every child of the current node, do the following:
       1. Assign temp = distance(root, current) + distance(current, child) + heuristic(child, goal).
       2. If temp < dis[child], then, assign dist[child] = temp. This denotes a shorter path to child node has been found.
       3. And, add child node to the queue if not already in the queue (thus, it's now marked as not visited again).
4. If queue is empty, then goal node was not found!

Why we need to re-add the nodes even if they are removed from set s in A* Vs Dijkstra, Or, Why we need to explore the nodes even if they are already visited in A* Vs Dijkstra?

Consider the following tree, where the heuristic distance of A, E, F, G, N, & K to goal node equals to 15, 13, 2, 8, 6, & 8 respectively.

In Dijkstra, it considers only distance from the starting node. So, we would go A → F → E → G → K, or, A → E → F → G → K.

In A*, it considers both; distance from starting node + heuristics. So, we would go A → F → G → N → E → G → N → K, That’s because of the heuristics!.

In Dijkstra, we don’t explore a node V(remove from set s or mark it as visited) unless we guarantee the shortest path to this node. Because if you explored a node V, this means node V has the shortest path in the set from the root node, and there is no other shorter path to node V.

In other words, no way for any other node M (M!=V), where dis[M]+ distance(M, V) < dis[V].

But, In A*, we may miss the shortest path, and go to node G(and N), because of the heuristics. So, In A*, we need to re-explore the G(and N), and re-add it to the queue when a shorter path has been found, and hence, re-explore it’s children, because they are also affected by the new shorter path we found.

Finally, Download the source code for these algorithms, and share if you find it useful.