Finding shortest path travesal in matrix using

Question

Need to find the shortest path in this matrix for ex: if startnode is a1 and endnode is b6 the o/p should be like this

[[0,0],[1,0],[1,1],[1,2],[1,3],[1,4],[1,5]]

My Matrix

    const matrix = [
      ["A1", "A2", "A3", "A4", "A5", "A6", "A7", "A8"],
      ["B1", "B2", "B3", "B4", "B5", "B6", "B7", "B8"],
      ["C1", "C2", "C3", "C4", "C5", "C6", "C7", "C8"],
      ["D1", "D2", "D3", "D4", "D5", "D6", "D7", "D8"],
      ["E1", "E2", "E3", "E4", "E5", "E6", "E7", "E8"],
      ["F1", "F2", "F3", "F4", "F5", "F6", "F7", "F8"],
      ["G1", "G2", "G3", "G4", "G5", "G6", "G7", "G8"],
      ["H1", "H2", "H3", "H4", "H5", "H6", "H7", "H8"]
    ];


    function findNode(node, nodeName) {
       let childNodeIdx = -1;
       const foundNode = matrix.find(fr => {
        const foundChildNode = fr.find(fc => {
         return fc.toLowerCase() === node.toLowerCase();
        });
        childNodeIdx = fr.indexOf(foundChildNode);
        return fr.includes(foundChildNode);
      });
    return { [nodeName]: [matrix.indexOf(foundNode), childNodeIdx] };
}

Function findWay

function findWay(position, end) {
  let queue = [];

  matrix[position[0]][position[1]] = 1;
  queue.push([position]);

  while (queue.length > 0) {
    const path = queue.shift();
    const pos = path[path.length - 1];

    const direction = [
      [pos[0] - 1, pos[1]],
      [pos[0], pos[1] - 1],
      [pos[0] + 1, pos[1]],
      [pos[0], pos[1] + 1]
    ];

    for (let i = 0; i < direction.length; i++) {
      // Perform this check first:      
      if (direction[i][0] == end[0] && direction[i][1] == end[1]) {
        return path.concat([end]);
      }

      if (
         direction[i][0] >= matrix[0].length ||
         direction[i][1] >= matrix[0].length
      ) {
        continue;
      }
      if (direction[i][0] >= 0 && [direction[i][1]] >= 0) {
        matrix[direction[i][0]][direction[i][1]] = 1;
        // extend and push the path on the queue
        queue.push(path.concat([direction[i]]));
      }
    }
  }
}

const start = findNode("a1", "startNode").startNode;
const end = findNode("b6", "endNode").endNode;

const path = findWay(start, end);
console.log(JSON.stringify(path));

this code works fine for short start and end nodes like a1 and b6 but when start node a1 and end node is e8 it takes longer time to print the o/p. I need to know how to solve the time complexity here in the problem

Rule is move vertically and hirizontally but not diagonally Any help would be appreciated

Answer 1

Not sure if I understand your problem correctly. Please check this snippet out:

const matrix = [
      ["A1", "A2", "A3", "A4", "A5", "A6", "A7", "A8"],
      ["B1", "B2", "B3", "B4", "B5", "B6", "B7", "B8"],
      ["C1", "C2", "C3", "C4", "C5", "C6", "C7", "C8"],
      ["D1", "D2", "D3", "D4", "D5", "D6", "D7", "D8"],
      ["E1", "E2", "E3", "E4", "E5", "E6", "E7", "E8"],
      ["F1", "F2", "F3", "F4", "F5", "F6", "F7", "F8"],
      ["G1", "G2", "G3", "G4", "G5", "G6", "G7", "G8"],
      ["H1", "H2", "H3", "H4", "H5", "H6", "H7", "H8"]
    ];


    function findNode(node, nodeName) {
       let childNodeIdx = -1;
       const foundNode = matrix.find(fr => {
        const foundChildNode = fr.find(fc => {
         return fc.toLowerCase() === node.toLowerCase();
        });
        childNodeIdx = fr.indexOf(foundChildNode);
        return fr.includes(foundChildNode);
      });
    return { [nodeName]: [matrix.indexOf(foundNode), childNodeIdx] };
}

  function findPath(startValue,endValue) {
let output = [];
let startNodeX = findNode(startValue, "startNode").startNode[0];
let startNodeY = findNode(startValue, "startNode").startNode[1];
let endNodeX = findNode(endValue, "endNode").endNode[0];
let endNodeY = findNode(endValue, "endNode").endNode[1];
while (Math.abs(startNodeX - endNodeX) > 0) {
   while (Math.abs(startNodeY - endNodeY) > 0) {
      output.push([startNodeX,startNodeY]);
      startNodeY>endNodeY ? startNodeY-- : startNodeY++;
   }
   output.push([startNodeX,startNodeY]);
   startNodeX>endNodeX ? startNodeX-- : startNodeX++;
}
output.push([endNodeX,endNodeY]);
return output;
  };
  const t1 = findPath("a1","b6");
  const t2 = findPath("f1","a1");
  const t3 = findPath("f6","b2");
  console.log(t1);  console.log(t2);  console.log(t3);

Answer 2

const findPath = (from, to) => {
   const locate = x => ['ABCDEFGH'.indexOf(x[0].toUpperCase()), x[1] - 1];
   const [start, end] = [locate(from), locate(to)];
   const path = [start];
   const [rowDirection, columnDirection] = [Math.sign(end[0] - start[0]), Math.sign(end[1] - start[1])];
   while (rowDirection * (path[path.length - 1][0] - end[0]) < 0) 
	 path.push([path[path.length - 1][0] + rowDirection, path[path.length - 1][1]]);
   while (columnDirection * (path[path.length - 1][1] - end[1]) < 0) 
	 path.push([path[path.length - 1][0], path[path.length - 1][1] + columnDirection]);
   return path;
}
console.log(JSON.stringify(findPath('a1', 'b6')));
console.log(JSON.stringify(findPath('a1', 'e8')));
console.log(JSON.stringify(findPath('e8', 'e1')));
console.log(JSON.stringify(findPath('e8', 'c8')));
console.log(JSON.stringify(findPath('f1', 'a1')));

Answer 3

The reason your algorithm is slow for long paths is that you are not marking the cells you have visited. When you have a cell in the queue, you are adding its neighbors to the queue even if they have been already visited.

I am not very familiar with javascript, but in other languages such as Java or Python you can use a HashSet in this case to check whether a cell has been visited in a constant time complexity before adding it to the queue.

Adding this will result in a global time complexity of O(N) where N is the size of the matrix given that you are not visiting a cell twice.