ダイクストラ法

dijkstra.scala

object Dijkstra extends Application {

  case class Node(id: Int)

  val graph = Map(
    Node(0) -> Map(Node(1) -> 5, Node(2) -> 4, Node(3) -> 2),
    Node(1) -> Map(Node(0) -> 5, Node(2) -> 2, Node(5) -> 6),
    Node(2) -> Map(Node(0) -> 4, Node(1) -> 2, Node(3) -> 3, Node(4) -> 2),
    Node(3) -> Map(Node(0) -> 2, Node(2) -> 3, Node(4) -> 6),
    Node(4) -> Map(Node(2) -> 2, Node(3) -> 6, Node(5) -> 4),
    Node(5) -> Map(Node(1) -> 6, Node(4) -> 4)
  )

  def dijkstra(routes: Map[List[Node], Int]) : (Map[List[Node], Int]) = {
    val scanned = routes.flatMap {
      case (route, cost) => {
        graph(route(0)).flatMap {
          case (n, c) if routes.forall(_._1(0) != n) => Some((n :: route) -> (cost + c))
          case _ => None
        }
      }
    }
    if(scanned.isEmpty) {
      routes
    }
    else {
      dijkstra(routes + scanned.reduceLeft { (a, b) => if(a._2 < b._2) a else b })
    }
  }

  println(dijkstra(Map(List(Node(0)) -> 0)))

}

実行すると

Map(
  List(Node(0)) -> 0,
  List(Node(5), Node(4), Node(2), Node(0)) -> 10,
  List(Node(3), Node(0)) -> 2,
  List(Node(4), Node(2), Node(0)) -> 6,
  List(Node(1), Node(0)) -> 5,
  List(Node(2), Node(0)) -> 4
)

のように、各ノードへの最短経路がその時のコストと共に表示されます。
（上記は見やすいように空白・改行を入れてあります。）

途中計算を保持しないでワンステップずつすすむので、グラフが大きくなると破綻すると思われます。
まぁ、アルゴリズムの勉強用ということで。