BFS, который возвращает кратчайший путь на втором массиве/невзвешенном графе

Я знаю, что об этом уже спрашивали, но я не могу понять решение из примеров и перевести их на javascript. даже при следующем: https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Например, у меня есть невзвешенный график или двумерный массив, который выглядит так:

const testMatrix = [
  [0, 0, 0, 0],
  [0, 0, 0, 0],
  [0, 1, 0, 0],
  [0, 1, 0, 0]
];

Затем я просматриваю это с помощью BFS: (в настоящее время я жестко запрограммировал элемент для поиска как элемент 2,2 в массиве). И верните список просмотренных элементов списка. но я не могу понять, как список увиденных должен показывать путь к кратчайшему пути.


const traversalBFS = function(matrix) {
  counter = 0;
  const seen = 
    new Array(matrix.length).fill(0).map(() => new Array(matrix[0].length).fill(false));

  const values = [];
  const queue = [[0, 0]];

  while(queue.length) {
    const currentPos = queue.shift();
    const row = currentPos[0];
    const col = currentPos[1];
    
    if(row < 0 || row >= matrix.length || col < 0 || col >= matrix[0].length || seen[row][col] || matrix[row][col] === 1) {
      continue;
    }

 

    counter++;
    seen[row][col] = true;
    values.push(matrix[row][col]);
     if(row === 2 && col === 2) {
        return seen;
    }
    
    for(let i = 0; i < directions.length; i++) {
      const currentDir = directions[i];
      queue.push([row + currentDir[0], col + currentDir[1]]);
    }
  }

  return false;
}

даже если я запускаю этот код

temp = traversalBFS(testMatrix);
let path = [];
for(i = 0; i <= 2; i++) {
  for(j = 0; j <= 2; j++) {
       if(temp[i][j]) {
          path.push([i, j]);
       }
  }
}

он вернется:

0: (2) [0, 0]
1: (2) [0, 1]
2: (2) [0, 2]
3: (2) [1, 0]
4: (2) [1, 1]
5: (2) [1, 2]
6: (2) [2, 0]
7: (2) [2, 2]

что никоим образом не является правильным путем, а также не является кратчайшим путем.

пример ожидаемого результата: хммм, скажем, конечная точка будет 1,1, а начальная будет 0, 0, ожидаемый результат - массив с кратчайшим путем:

[[0,0], [0, 1], [1,1]]

если начальная точка 0, 0, а конечная точка 2,2: я думаю, что результат должен быть:

[[0,0], [0, 1], [1,1],[1,2],[2,2];

используя тестовую матрицу, которую я написал в качестве примера. так как на пути нет 1 ака стен.


javascript dijkstra breadth-first-search
person Shaked Tayeb    schedule 18.04.2021    source источник
comment
у вас есть пример желаемого результата?   -  person Nina Scholz    schedule 18.04.2021
comment
хммм, скажем, конечная точка будет 1,1, а начальная будет 0, 0, ожидаемый результат - массив с кратчайшим путем: ``` [[0,0], [0, 1], [1,1]] ``` если начальная точка 0, 0, а конечная точка 2,2: я думаю, что результат должен быть: ``` [[0,0], [0, 1], [1,1],[ 1,2],[2,2]; ``` используя тестовую матрицу, которую я написал в качестве примера. так как на пути нет 1 ака стен.   -  person Shaked Tayeb    schedule 18.04.2021

Ответы (1)


arrow_upward
0
arrow_downward

Чтобы понять, как работает алгоритм Дейкстры, вы можете воспользоваться подходом по данной ссылке и взять большое значение для начала и взять меньшие значения, как только они появятся у соседей.

В этом примере вместо индексов используются значения (шага), но их можно заменить координатами пути к цели.

Этот подход использует обход препятствий и короткое замыкание, если цель найдена.

const
    travel = (array, from, to) => {
        const
            go = (i, j, smallest) => {
                if (array[i]?.[j] === 1) return;
                if (i === to[0] && j === to[1]) return;
                if (unvisited[i]?.[j] > smallest) {
                    unvisited[i][j] = smallest;
                    go(i + 1, j, smallest + 1);
                    go(i - 1, j, smallest + 1);
                    go(i, j + 1, smallest + 1);
                    go(i, j - 1, smallest + 1);
                }
            },
            unvisited = testMatrix.map(a => a.map(_ => Number.MAX_VALUE));

        go(from[0], from[1], 0);
        return unvisited;
    },
    testMatrix = [[0, 0, 0, 0], [0, 0, 0, 0], [0, 1, 0, 0], [0, 1, 0, 0]],
    result = travel(testMatrix, [0, 0], [3, 2]);

result.forEach(a => console.log(a.map(v => v === Number.MAX_VALUE ?'*': v).join(' ')));

person Nina Scholz    schedule 18.04.2021