Path Finding Algos

 Breadth First Search(BFS)

Breadth first search's principle is quite simple, traverse level by level until we find the destination. Now, in a grid system we can traverse by making a radial expansion having center as the source cell. So you may see such visualization which is quite self explanatory. But how do you implement that?

Algorithm:

1. Make a queue and push the source vertex in it. 

2. while(q.length!=0)

1. Pop the element from stack
2. check if any of points (x+1,y), (x,y+1),(x-1,y) and (x,y-1) are destination vertex.
3. If yes: return
4. If no: push  (x+1,y), (x,y+1),(x-1,y) and (x,y-1) into stack.

Code: 

class QItem { 
public: 
    int row; 
    int col; 
    int dist; 
    QItem(int x, int y, int w) 
        : row(x), col(y), dist(w) 
    { 
    } 
}; 
  
int minDistance(char grid[N][M]) 
{ 
    QItem source(0, 0, 0); 
  
    // To keep track of visited QItems. Marking 
    // blocked cells as visited. 
    bool visited[N][M]; 
    for (int i = 0; i < N; i++) { 
        for (int j = 0; j < M; j++) 
        { 
            if (grid[i][j] == '0') 
                visited[i][j] = true; 
            else
                visited[i][j] = false; 
  
            // Finding source 
            if (grid[i][j] == 's') 
            { 
               source.row = i; 
               source.col = j; 
            } 
        } 
    } 
  
    // applying BFS on matrix cells starting from source 
    queue<QItem> q; 
    q.push(source); 
    visited[source.row][source.col] = true; 
    while (!q.empty()) { 
        QItem p = q.front(); 
        q.pop(); 
  
        // Destination found; 
        if (grid[p.row][p.col] == 'd') 
            return p.dist; 
  
        // moving up 
        if (p.row - 1 >= 0 && 
            visited[p.row - 1][p.col] == false) { 
            q.push(QItem(p.row - 1, p.col, p.dist + 1)); 
            visited[p.row - 1][p.col] = true; 
        } 
  
        // moving down 
        if (p.row + 1 < N && 
            visited[p.row + 1][p.col] == false) { 
            q.push(QItem(p.row + 1, p.col, p.dist + 1)); 
            visited[p.row + 1][p.col] = true; 
        } 
  
        // moving left 
        if (p.col - 1 >= 0 && 
            visited[p.row][p.col - 1] == false) { 
            q.push(QItem(p.row, p.col - 1, p.dist + 1)); 
            visited[p.row][p.col - 1] = true; 
        } 
  
         // moving right 
        if (p.col + 1 < M && 
            visited[p.row][p.col + 1] == false) { 
            q.push(QItem(p.row, p.col + 1, p.dist + 1)); 
            visited[p.row][p.col + 1] = true; 
        } 
    } 
    return -1; 
} 

Depth First Search(DFS)

Its algo is just opposite of the breadth first search where we traverse level by leve. Here we just reach end by traversing through all levels in one go. We do not reach all nodes of all levels at one go but traverse them many times until all othem are reached.

Code:

function dfs_on_grid(x, y) {	

        if(fl)

            return;

        if(x==endX&&y==endY){

            cout<<"Reached end";

            fl=1;

            return;

        }
	if (isValid(x - 1, y)) {
	    dfs_on_grid(x - 1, y);
        }
	if (isValid(x, y - 1)) {	
	    dfs_on_grid(x, y - 1);
	}
	if (isValid(x + 1, y)) {
            dfs_on_grid(x + 1, y)		
	}
	if (isValid(x, y + 1)) {		

	    dfs_on_grid(x, y + 1)		
	}
}