从棋盘构建邻接图（用于 dijkstra）

Question

我运行遇到了一个问题，我想在作业中添加一些功能，但结果却让我不知所措（在没有上下文的情况下阅读粗体句子）。

我的程序有一个包含大约 35 个项目的列表，其中包含有关我应该使用的地图的信息。它可以包含以下元素：

"Wall" 及其坐标 (X, Y)，在 dijkstra 中它的权重应该是 100。
"Tree" 带绳索 (X, Y)，重量 3

我有一张像棋盘一样布局的 10x10 地图，这意味着 100 个图块和 35 个项目。列表中的"Nothing"表示dijkstra中权重为1（表示正常路由）

为了使 dijkstra 工作并能够找到两个图块之间的最短路径，我必须构建一个邻接图。 我的问题是，如何定义图块 "around" 当前图块，如果我只有那个列表？

只有“+”形状的相邻图块在它们之间的图形中有边，但我每次都必须运行通过列表来检查是否上面有东西吗？

任何关于这个问题的线索都将不胜感激，如果你能给我指出一个带有代码示例的源代码，那也可以。我只看到非常混乱的代码，其中有很多 "if-elseif-elseif..." 来解决这个问题。

感谢您的宝贵时间！

编辑：我最终使用了@kraskevich 的建议方式，效果很好，但所有的答案和建议都非常有用，非常感谢大家！

Answer 1

您真的不需要构建图表。只需要创建一个10x10 table，然后将对应物品的重量放入其中即可：

board = 10x10 array filled with 1
for item in list:
    if item is a tree:
         board[item.row][item.column] = 3
    else if item is a wall:
         board[item.row][item.column] = 100

之后，您可以将坐标对 (row, col) 视为顶点，并在处理图块时更新 4 个相邻单元格的距离。而已。当然，您也可以创建一个包含 100 个顶点的图，并从一个图块明确地将边添加到所有 4 个相邻单元格（权重是边图块末端的权重）并使用标准实现。

迭代相邻单元格最方便的方法如下：

delta_rows = [-1, 1, 0, 0]
delta_cols = [0, 0, -1, 1]
...
for direction = 0 .. 3
     new_row = row + delta_rows[direction]
     new_col = col + delta_cols[direction]
     if is_valid(new_row, new_col)
          // do something

Answer 2

基于这个通用图形接口实现 Dijkstra 应该很简单：

interface Graph<T> {
  Iterable<T> adjacentNodes(T node);
  double getDistance(T node, T adjacent);
}

所以现在我们需要做的就是为您填写它：

class Field {
  final int x;
  final int y;
  int value = 1;
  Field (int x, int y) {
    this.x = x;
    this.y = y;
  }
}

class ChessboardGraph implements Graph<Field> {
  Field[][] board = new Filed[10][10];

  ChessboardGraph(List<Entry> list) {
    for (int x = 0; x < 10; x++) {
      for (int y = 0; y < 10; y++) {
        board[x][y] = new Field(x, y);
      }
    }
    for (Entry e: list) {
      board[e.x][e.y].value = e.value == TREE ? 3 : 100;
    }
  }

  Iterable<Field> adjacentNodes(Field node) {
    ArrayList result = new ArrayList<>();
    int x = node.x;
    int y = node.y;
    if (x > 0) {
      if (y > 0) {
        result.add(board[x - 1][y - 1]);
      }
      if (y < 9) {
        result.add(board[x - 1][y + 1]);
      }
    }
    if (x < 9) {
      if (y > 0) {
        result.add(board[x + 1][y - 1]);
      }
      if (y < 9) {
        result.add(board[x + 1][y + 1]);
      }
    }
  }

  double getDistance(Field node, Field adjacent) {
    assert Math.abs(node.x - adjacent.x) + Math.abs(node.y - adjacent.y) == 1;
    return board[adjacent.x][adjacent.y];
  }
}

从棋盘构建邻接图（用于 dijkstra）

Building adjacency graph out of chessboard (for dijkstra)

algorithm

dijkstra

matrix

adjacency-matrix

graph-algorithm