Как сделать алгоритм Дейкстры на матрице сетки - PullRequest
Новая
       92

Как сделать алгоритм Дейкстры на матрице сетки

0 голосов
/ 01 мая 2020

Итак, у меня есть опоясывающий лишний размер, который может быть любого заданного размера (например, матрица или 2d массив) Каждый элемент содержит значение, и мне просто нужно найти кратчайший путь. Однако проблема, с которой я сталкиваюсь, состоит в том, чтобы попытаться представить эту сетку в виде графа или вспомогательной матрицы или того, что вы когда-либо должны были делать. Например, это мой код: 

public int shortestPath (int[][] matrix, int sr, int sc, int dr, int dc)
{
    int p = matrix.length * matrix[0].length;
    int[] distances = new int[p];
    boolean[] visited = new boolean[p]; //I think all are set to false by default

    for (int i = 0; i < p; i++)
    {
        distances[i] = Integer.MAX_VALUE;
    }

    PriorityQueue<Node> pq = new Priority<>(); // a Node holds the int row, int col and the distance from source cell. It also orders by distances, so therefore a comparable was created to change natural order.
    pq.add(new Node(sr,sc,0);
    distances[(sr * matrix[0].length) + sc] = 0;
    visited[(sr * matrix[0].length) + sc] = true;

    while(!pq.isEmpty())
    {
        Node n = pq.poll();
        int row = n.getRow();
        int col = n.getColumn();
        int dist = n.getDistance();

     //Now here with a normal graph I would search neighbours via a for loop and find in the adj list where an element = 1 and is not visited. This is where I am stuck
    }
}

Итак, очевидно, что с сеткой мне нужно будет найти соседей влево / вправо / вверх / вниз (без диагоналей). Таким образом, мне нужно учитывать границы. Как можно создать матрицу Adj или как правильно начать поиск соседей для такой сетки?

Мне сегодня не повезло с этим, потому что большинство примеров показано в графической форме для матрицы смежности, а не из Форма сетки для прилегающей матрицы.

1 Ответ

1 голос
/ 01 мая 2020

Для графиков сетки есть хитрость:

  1. Допустим, {x, y} обозначает разницу между двумя соседними ячейками
  2. Вы знаете, что соседи будут в {0, -1} , {0,1}, {1,0} или {-1,0} (при условии отсутствия диагональных перемещений), или эти ячейки будут выходить за пределы
  3. Сохранить массивы этих различий: 
int differenceX[] = {0,0,1,-1};
int differenceY[] = {-1,1,0,0};
Теперь вы можете использовать для l oop для соседей: 
    for(int i=0; i<4; i++)
    {
        int neighRow = row + differenceY[i];
        int neighCol = col + differenceX[i];
        if(min(neighRow, neighCol) >= 0 && neighRow < matrix.length && neighCol < matrix[0].length){
            //process node
        }
    }
...