Finding shortest and longest distance using depth first search in a weighted grid by traversing all four directions

56 Views Asked by At

I am trying to do a Dfs on a weighted grid to find both the shortest distance and longest distance to reach from the index 0,0 to the end cell in the bottom right corner.

I know this can be achieved using the Dijkstra algorithm, but I am just trying to do it using DFS and practice so that I can hone my skills.

In the grid, from each cell, we can traverse in all four directions.

I have written the code for finding the shortest distance and it works fine.

var grid = [  [1, 3, 1],
[3, 3, 3],
[3, 3, 2]]

let directions = [[-1,0], [1, 0], [0,-1], [0,1]]

let ROWS = grid.length;
let COLS = grid[0].length;
let costMatrix = new Array(ROWS).fill().map(() => new Array(COLS).fill(Infinity));
costMatrix[0][0] = 0;

dfs(grid, 0, 0, costMatrix);


function dfs(grid, row, col, distance)
{
   
    let currentValue = grid[row][col];
    grid[row][col] = -1 //set to visited;

    for(var dir of directions){
        let [dx, dy] = dir;
        let newDx = row+dx;
        let newDy = col+dy;

        // out of bounds check
        if(newDx < 0 || newDx >= ROWS || newDy < 0 || newDy >= COLS)
            continue;

        // if the node is already visited
        if(grid[newDx][newDy] == -1)
            continue;

        let currentDistance = distance[newDx][newDy];
        if( currentDistance > distance[row][col]+grid[newDx][newDy])
                distance[newDx][newDy] = distance[row][col]+grid[newDx][newDy];

        dfs(grid, newDx, newDy, distance)
    }

    grid[row][col] = currentValue;

    return;
}

console.log(costMatrix[ROWS-1][COLS-1]);

But I am not sure how can I change this program to find the maximum distance. If I change the Infinity to -Infinity and this condition currentDistance > distance[row][col]+grid[newDx][newDy] from greater than to lesser than. It doesn't work because it is going to be always lesser than as we add the weights everytime we traverse.

So could someone please explain how to visualize the Dfs traversal to solve this problem, which involves traversing all four directions.

0

There are 0 best solutions below