ダイクストラ法

ダイクストラ法をRとigraphを使って表現する．

igraphのshortest.paths関数で一発でできるのだけど，お勉強のためということで．

まずは最短経路を求めるグラフを用意する．

library(igraph)
g<-graph.empty(5)
V(g)$name<-c("A","B","C","D","E")
g<-add.edges(g,c(0,1,0,2,0,3,1,2,1,3,1,4,2,3,3,4))
g<-as.undirected(g)
E(g)$weight<-c(2,1,7,5,6,1,1,8)
lay<-rbind(c(1,3),c(2,3),c(1,1),c(2,1),c(3,2))
plot(g, layout=lay,vertex.label=V(g)$name,vertex.size=12,edge.label=E(g)$weight)

こんな感じ．今回はノード「E」をゴールとする．

つぎに各ノードのコストを初期化する．

V(g)$cost<-c(Inf,Inf,Inf,Inf,0)
V(g)$fixed=FALSE
V(g)$color<-"skyblue"
plot(g, layout=lay,vertex.label=V(g)$cost,vertex.size=12,edge.label=E(g)$weight,vertex.color=V(g)$color)

つぎはコスト計算．

V(g)[nei(V(g)[fixed==FALSE & cost==min(V(g)[fixed==FALSE]$cost)]) & fixed==FALSE][V(g)[nei(V(g)[fixed==FALSE & cost==min(V(g)[fixed==FALSE]$cost)]) & fixed==FALSE]$cost>(E(g)[V(g)[fixed==FALSE] %->% V(g)[fixed==FALSE & cost==min(V(g)[fixed==FALSE]$cost)]]$weight)+(V(g)[fixed==FALSE & cost==min(V(g)[fixed==FALSE]$cost)]$cost)]$cost<-(E(g)[V(g)[fixed==FALSE] %->% V(g)[fixed==FALSE & cost==min(V(g)[fixed==FALSE]$cost)]]$weight)+(V(g)[fixed==FALSE & cost==min(V(g)[fixed==FALSE]$cost)]$cost)

ながい．．．もっと短くできるかもしれない．

V(g)[fixed==FALSE & cost==min(V(g)[fixed==FALSE]$cost)]$color="yellow"
V(g)[fixed==FALSE & cost==min(V(g)[fixed==FALSE]$cost)]$fixed=TRUE

計算が終わったノードは黄色に塗りつぶす．

plot(g, layout=lay,vertex.label=V(g)$cost,vertex.size=12,edge.label=E(g)$weight,vertex.color=V(g)$color)

これを計算するノードが無くなるまで繰り返す．

もう一回．

もう一回．

もう一回．

もう一回．

これで終わり．

実際にグラフを描きながらだと楽しいね．