R でグラフ理論
library(igraph) #エッジリストの作成 d <- data.frame(matrix(c( "s","a", "s","b", "a","b", "a","c", "a","d", "b","a", "b","c", "b","d", "c","d", "c","e", "c","f", "d","a", "d","b", "d","f", "e","d", "e","z", "f","e", "f","z"),nc=2,byrow=TRUE),stringsAsFactors=FALSE) colnames(d) <- c("from","to") #ノードリストの作成 vers <- data.frame(c("s","a","b","c","d","e","f","z"),stringsAsFactors=FALSE) #グラフの作成 g <- graph.data.frame(d,directed=TRUE,vertices=vers) #ウエイトの指定 E(g)$weight <- c(3,5,1,10,11,3,2,3,2,7,12,15,7,2,11,2,3,2) #ノードの座標の指定 vs <- c(1,2); va <- c(3,3); vb <- c(3,1); vc <- c(5,3); vd <- c(5,1); ve <- c(7,3); vf <- c(7,1); vz <- c(9,2) lay <- rbind(vs,va,vb,vc,vd,ve,vf,vz) #プロット par(mfrow=c(1,2),oma=c(0,0,0,0)) plot(g,layout=lay,vertex.label=V(g)$name,edge.label=E(g)$weight) #最短経路の計算 spv <- shortest.paths(g, v=0,mode="out") sp <- get.shortest.paths(g,from=0,to=7) V(g)$color <- "lightblue" V(g)$color[(unlist(sp)+1)] <- "red" E(g)$width <- 1 E(g,path=unlist(sp))$width <- 3 plot(g,layout=lay,vertex.label=spv,edge.label=E(g)$weight)左の図が与えられたグラフです。いま求めたいのは、sからzへの最短経路です。辺の上にある正の数は重みを表し、実際には所要時間に相当します。igraphでは、2つのノードを直接結ぶ辺を複数持つ、多重グラフがうまく表現できないのが難点です。