Вычислить матрицу смежности в R из матрицы nxm (представляющую карту)

Question

Я новичок в R, и я играю с играфом и маршрутами. У меня есть матрица, которую можно рассматривать как карту (координаты x и y). 0 - проходное пространство, а 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 

Цель состоит в том, чтобы рассчитать кратчайший путь от верхней левой точки до нижней правой точки. Движимые способы - это левое/правое/верхнее/нижнее и диагональное, но препятствие (обозначенное 1 значением матрицы) не может быть передано.

Я нашел способы использовать Dijkstra на матрице смежности в R из похожих вопросов, но я не нашел способ использовать его в этой примерной матрице (представляющей карту/пол). Следовательно, I хотел узнать, есть ли простой способ (например, функция) создать матрицу смежности с этого входа?

---

Пример вдохновлен Дейкстра Википедии Страница https://en.wikipedia.org/wiki/Dijkstras_algorithm#Algorithm

Особенно от GIF, где препятствие блокирует прямой путь. (Я бы опубликовал 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")