simudaru's blog

Python, Rなどのメモを残していこうと思います。  よろしくお願いいたします。

【R】e1071パッケージのallShortesPath関数を試しました

Rのe1071パッケージ、allShortesPathを試してみました。

有向グラフあるいは無向グラフの、ノード間の最短距離を計算する関数です。
計算にはワーシャル-フロイド法を使っているとのことです。

# allShortesPathとextractPathについて
library(e1071)

# 5nodesの有向グラフを作成
# x[i, j]の値の意味は、iからjまでの重み付き距離
x <- matrix(NA, 5, 5)
diag(x) <- 0
x[1, 2] <- 30; x[1, 3] <- 10
x[2, 4] <- 70; x[2, 5] <- 40
x[3, 4] <- 50; x[3, 5] <- 20
x[4, 5] <- 60
x[5, 4] <- 10
print(x)

if(0){'
  x の中身
      [,1] [,2] [,3] [,4] [,5]
  [1,]    0   30   10   NA   NA
  [2,]   NA    0   NA   70   40
  [3,]   NA   NA    0   50   20
  [4,]   NA   NA   NA    0   60
  [5,]   NA   NA   NA   10    0  
'}

# ワーシャル-フロイド法により、全ての点について、最短距離と経路を求める
z <- allShortestPaths(x)
print(z)
if(0){'
$length
     [,1] [,2] [,3] [,4] [,5]
[1,]    0   30   10   40   30
[2,]   NA    0   NA   50   40
[3,]   NA   NA    0   30   20
[4,]   NA   NA   NA    0   60
[5,]   NA   NA   NA   10    0

$middlePoints
     [,1] [,2] [,3] [,4] [,5]
[1,]    0    0    0    5    3
[2,]    0    0    0    5    0
[3,]    0    0    0    5    0
[4,]    0    0    0    0    0
[5,]    0    0    0    0    0
'}

# node「1」からnode「4」への最短経路
extractPath(z, 1, 4)
if(0){'
[1] 1 3 5 4
'}
# 1→3→5→4が最短経路

あまり使う機会はないかもしれないですが、
こういう関数もあるということは覚えておこうと思います。