Problem 82 - Project Euler
引き続いて最短経路問題。
データはProblem 81と一緒だけど、開始ノードと目標ノードがそれぞれ複数候補を持っている。こういうときのアルゴリズムってあるのかな。
ちょっと無理矢理問いた感じはあるけどなんとか1分以内には終わった。40秒。
library(igraph) mtrx <- read.table("matrix.txt",sep=",") nodeid <- matrix(1:(80*80), 80, 80) edge <- numeric(0) weight <- numeric(0) for(i in 1:79){ edge <- c(edge, nodeid[1,i], nodeid[1,i+1], nodeid[1,i], nodeid[1+1,i] ) weight <- c(weight, mtrx[1,i+1], mtrx[1+1,i] ) for(j in 2:79){ edge <- c(edge, nodeid[j,i], nodeid[j-1,i], nodeid[j,i], nodeid[j,i+1], nodeid[j,i], nodeid[j+1,i] ) weight <- c(weight, mtrx[j-1,i], mtrx[j,i+1], mtrx[j+1,i] ) } edge <- c(edge, nodeid[80,i], nodeid[80,i+1], nodeid[80,i], nodeid[80-1,i] ) weight <- c(weight, mtrx[80,i+1], mtrx[80-1,i] ) } edge <- data.frame(matrix(edge, nc=2, byrow=T)) g <- graph.data.frame(edge,directed=TRUE, vertices=as.vector(nodeid)) E(g)$weight <- weight sums <- function(a) sum(as.vector(as.matrix(mtrx))[a+1]) ans <- 10000000 for(i in 1:80){ paths <- get.shortest.paths(g, from=nodeid[i,1]-1, to=nodeid[,80]-1, mode="out" ) cand <- min(as.numeric(as.matrix(lapply(paths,sums)))) if(ans>cand) ans <- cand } ans