从nxm矩阵（代表地图）计算R中的邻接矩阵

Question

我是 R 的新手，正在研究 igraph 和路由。我有一个矩阵，可以看作是一个地图（x 和 y 坐标）。 0 是可步行的 space，1 是障碍物。示例矩阵为：

0   0   0   0   0   0   0
0   0   0   1   1   0   0
0   0   0   1   1   0   0
0   0   1   1   1   0   0
0   0   1   1   1   0   0
0   0   0   0   0   0   0

目标是计算从左上角点到右下角点的最短路径。可移动的路有left/right/top/down和对角线，但路中的障碍物（矩阵的1值表示）不能通过

我从类似的问题中找到了在 R 中的邻接矩阵上使用 Dijkstra 的方法，但我没有找到在这个示例矩阵（代表 map/floor）上使用它的方法。因此我想知道是否有一种简单的方法（如函数）从该输入创建邻接矩阵？

该示例的灵感来自 Dijkstra 维基百科页面 https://en.wikipedia.org/wiki/Dijkstras_algorithm#Algorithm

尤其是 GIF 中有障碍物挡住了直接的路。（我会 post GIF，但我没有足够的声誉）

Answer 1

我认为这就是您所追求的。我正在使用 igraph 版本 1 表示法。

> packageVersion("igraph")
[1] ‘1.0.1’

想法是创建一个 2D 网格，然后移除阻塞的节点或（在本例中）移除任何附加到它们的边。

library(igraph)
# Your grid in matrix form
grid <- rbind(c(0,   0,   0,   0,   0,   0,   0),
              c(0,   0,   0,   1,   1,   0,   0),
              c(0,   0,   0,   1,   1,   0,   0),
              c(0,   0,   1,   1,   1,   0,   0),
              c(0,   0,   1,   1,   1,   0,   0),
              c(0,   0,   0,   0,   0,   0,   0))

# Make a network on a 2D grid
g <- make_lattice(dimvector=c(nrow(grid), ncol(grid)))

# Add a colour for the nodes we'll be disconnecting
V(g)$color <- c('orange', 'blue')[as.numeric(grid==1)+1]
plot(g)

# Disconnect the inpassable nodes
gGap <- g - E(g)[inc(V(g)[grid==1])]
plot(gGap)

# Either output the adjacency matrix and do your own thing
as_adjacency_matrix(gGap,sparse = FALSE)

# Or find distances in igraph
distances(gGap, v=V(gGap)[1], to=V(gGap), algorithm="dijkstra")

从nxm矩阵（代表地图）计算R中的邻接矩阵

Calculate Adjacency Matrix in R from nxm matrix (representing the map)

r

dijkstra

adjacency-matrix