グラフのペアワイズ最短距離と最短経路

• グラフのペアワイズ最短距離が出したいことがある
• 密グラフならWarshall-Floyd、疎グラフならJonhsonが効率的という(参考)
• RのigraphパッケージもRGBLパッケージも最短距離は計算してくれるのだが、Warshall-Floydの行列が欲しい(どうしてほしくなるかはここでは問わないとして…)とすると、それを返してくれるわけではなく、WFとJohnsonのどちらが効率的かを判断して、よい方で計算して返してくれるらしいので、探し物をした
• e1071という膨大な関数のパッケージにWF行列を返してくれる関数 allShortestPaths() があったので、メモ

library(e1071)
library(igraph)
# g はigraphのグラフオブジェクト
# w はエッジの重みベクトル
my.WarshallFloyd <- function(g,w){
  v <- V(g)
  E(g)$weight <- w

  d <- as_adjacency_matrix(g,attr="weight")
  d <- as.matrix(d)
  d[which(d==0)] <- NA
  sh <- allShortestPaths(d)
  return(sh)
}
sh <- my.WarshallFloyd(g,w)
# shは最短距離行列と最短パスを取り出す情報行列とから成る
#sh
i <- 3
j <- 5
extractPath(sh,i,j)