ダイクストラ法はグラフ理論における最短経路問題を解くためのアルゴリズム

dikstra.scala

import scala.annotation.tailrec

  /*
   [C] >2 [A] >2 [E]
     \       >1 [D]
      \      >1
       \        \
       >1 [B] >6 [F]

   C>A>F が最短

  // 遷移先をPriorityQueueにいれる。 (既に訪問済みだったら、今回のコストが小さい場合、そこまでの最短経路に上書きでいれる)
  // 既に訪問済みの場合は辿らない。
  // 遷移先がなくなるまで辿る。
  // 最後にゴールからfromを辿り最短距離を取得する。(既に訪問済みの場合、コストが小さいほうを優先してるので最短になってる)
  */

object Main {
  def main(args: Array[String]) {
    dikstra(sampleGraph).map(println)
  }

  case class Graph(es: Map[Vertex, Seq[Edge]])
  case class Vertex(name: String)
  case class Edge(v: Vertex, weight: Int, from: Option[Edge] = None) extends Ordered[Edge] {
    def compare(e: Edge): Int = e.weight - weight
  }
  type Path = Map[Vertex, Edge]

  def sampleGraph: Graph = Graph(
    Map(
      Vertex("C") -> Seq(Edge(Vertex("A"), 2), Edge(Vertex("B"), 1)),
      Vertex("A") -> Seq(Edge(Vertex("E"), 2), Edge(Vertex("D"), 1), Edge(Vertex("F"), 1)),
      Vertex("B") -> Seq(Edge(Vertex("F"), 6))
    )
  )

  def dikstra(g: Graph): Seq[Vertex] = {
    val start = Vertex("C")
    val goal = Vertex("F")
    val path = dikstra(g, start, goal)
    path.get(goal).map(shortestPath(_)).getOrElse(Nil) // startからgoalまでの最短距離を取得
  }
  @tailrec
  def shortestPath(e: Edge, r: Seq[Vertex] = Nil): Seq[Vertex] = e.from match {
    case Some(ef) => shortestPath(ef, e.v +: r)
    case None => e.v +: r
  }

  def dikstra(g: Graph, start: Vertex, goal: Vertex): Path = {
    val q = scala.collection.mutable.PriorityQueue[Edge]()
    q += Edge(start, 0)

    @tailrec
    def search(path: Path = Map()): Path = {
      if (q.isEmpty) path
      else {
        val edge = q.dequeue()
        g.es.get(edge.v).map { _.foreach { e =>
          if (!path.contains(e.v)) q += Edge(e.v, edge.weight + e.weight, Some(edge)) // 遷移先を登録
        }}
        val ne = path.get(edge.v).map(e => if (edge.weight < e.weight) edge else e).getOrElse(edge) // 訪問済みなら小さいほう優先
        search(path + (edge.v -> ne))
      }
    }
    search(Map(start -> Edge(start, 0)))
  }
}