(R) igraphパッケージを使って最短経路探索をweightつきで計算する。

探してもドンピシャの結果がなかったので自分で書くしかない

追記

Twitterの自動投稿を見て気づいたんですが、「最短経路探索」って書いてありますが、実際には経路を探索はしていなくて、この場合は任意の２点間のコストを最小にする経路を通った時のコストが返ってきています。なので、最短経路は探索していますが、経路そのものはわからず、最小のコストだけがわかる、ということです（タイトルはまぁどっちともとれるから変更せずで良いかな…）。紛らわしいので追記しました。

---

本題

さて、任意の2点間の経路の最短経路を見つけたい、ただしそれぞれの経路には向きがある上にweightが設定されているものとする。任意の２点間を結ぶ経路は直接でもよいし、ない場合はほかの点を経由してもよい。とにかくたどり着けばよく、その中で経路のコストが最小の値を知りたい、ということが目的です。

# 準備
library(igraph)
library(tidyverse)
library(ggraph)

# data.frameを作る
df <- data.frame(from=c(1,2,2,2,3,3,4), 
                   to=c(2,1,3,4,2,4,3), 
                   weight=c(0.7,1.3,1.7,0.7,1.7,1.7,1.2))

# data.frameからigraphのオブジェクトを作成する
g <- igraph::graph.data.frame(df)

# igraphオブジェクトを可視化
plot(g)

# igraphオブジェクトをDiagrammeRパッケージに渡して可視化
DiagrammeR::visnetwork(DiagrammeR::from_igraph(g))

# ggraphパッケージで可視化
ggraph(g) + geom_edge_link(aes(colour = factor(from))) + 
  geom_node_point()

# 経路を探索してもらう
igraph::shortest.paths(graph = g, mode="out")
#>     1   2   3   4
#> 1 0.0 0.7 2.4 1.4
#> 2 1.3 0.0 1.7 0.7
#> 3 3.0 1.7 0.0 1.7
#> 4 4.2 2.9 1.2 0.0

こんな感じでweightつきの経路探索ができました。実際に使いたいのはもっと多くの地点があるケースなので手作業で網羅するのが大変なので、このパッケージすごい便利だなぁと思った次第です。

graph系は可視化は沢山見かけるのですが、こういう計算系があまり見つからない気がしますね…。まぁ、関数１つで結果が出るので書くほどでもないからだろうか…。

igraphパッケージ、関数沢山あるので使いこなせれば便利かもしれませんね（難しそう）

Enjoy!!