如何在网格矩阵上执行dijkstra算法

Question

所以我有一个网格，可以是任何给定的大小(即矩阵或2d数组(。每个元素都包含一个值，我只需要找到最短的路径。然而，我遇到的问题是试图将这个网格表示为图形或adj矩阵，或者你打算做什么。例如，这是我的代码：

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矩阵，或者开始搜索类似网格的邻居的正确方法是什么？

我今天运气不好，因为大多数例子都是以图形形式显示到adj矩阵，而不是以网格形式显示到dj矩阵。

Answer 1

网格图有一个技巧：

1. 假设{x，y}表示2个相邻小区之间的差异
2. 你知道邻居将在｛0，-1｝，｛0,1｝，{1,0｝或｛-1,0｝中(假设没有对角线移动(，或者这些单元格将越界
3. 保存这些差异的数组：

int differenceX[] = {0,0,1,-1};
int differenceY[] = {-1,1,0,0};

4. 现在您可以为邻居使用for循环：

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
}
}