Problem 107

R Project Euler

最小全域木問題．3ms．やっぱこういうのは一度自分で作ってみると勉強になる．
プリム法を使った．

## 新たに確定したノードから直接到達可能なノードへのコストを更新
update.m.d <- function(min.dist, dec.velt, graph, dec.flag){
  comp <- min.dist > graph[dec.velt, ] # 新たに確定したノードから各ノードへの距離と比較
  ## 新たに確定したノードからの到達距離の方が短い部分を置き換える(未確定のノード)
  min.dist[comp & !dec.flag] <- graph[dec.velt,][comp & !dec.flag]
  return(min.dist)
}

## Prim's algorithm (コストのみ出力)
Prim <- function(graph){                # グラフは距離行列として与える
  min.dist <- rep(Inf, sqrt(length(graph))) # 確定ノードから各ノードへの最小コスト
  dec.flag <- rep(FALSE, length(min.dist))  # 確定フラグ
  min.dist[1] <- 0                      # 初期ノード確定
  dec.velt <- 1                         # 一つ前に確定したノード
  while(sum(!dec.flag) >= 1){           # 全てのノードが確定するまで
    min.dist <- update.m.d(min.dist, dec.velt, graph, dec.flag)
    dec.flag[dec.velt] <- TRUE          # 確定フラグ
    if(sum(!dec.flag) <= 1) break
    ## 確定フラグが立っていないノードのうち最も到達コストの小さいもの(の一つ目)を確定する
    dec.velt <- (1:length(min.dist))[!dec.flag][min.dist[!dec.flag] == min(min.dist[!dec.flag])][1]
  }
  return(min.dist)
}

## Problem 107
graph <- scan("network.txt", "character", sep=",")
graph[graph=="-"] <- Inf
graph <- matrix(as.numeric(graph), nrow=40)
sum(graph[!is.infinite(graph)])/2 - sum(Prim(graph))

プリム法，最小全域木問題については以下参考．