ベルマンフォード法は、重みつき有向グラフにおける単一始点の最短経路問題を解くラベル修正アルゴリズム。負の閉路(負の値により最短距離が更新され続けてしまうループ)を見つけることもできる。

bellmanFord.scala

import scala.annotation.tailrec

object Main {

  def main(args: Array[String]) {
    bellmanFord(sampleGraph, Vertex("C"))
      .toSeq.sortBy(_._2).map(println)
  }

  def bellmanFord(graph: Graph, start: Vertex): ShortestPath = {
    val initPath = graph.vertices.map { (_, Int.MaxValue) }.toMap.updated(start, 0)

    @tailrec
    def h(v: Vertex, es: Seq[Edge], sp: ShortestPath): ShortestPath = es match {
      case e :: et => {
        val oldCost = sp.get(e.v).get
        val newCost = sp.get(v).get + e.weight
        h(v, et, if (newCost < oldCost) sp.updated(e.v, newCost) else sp) // 小さい場合は最短距離を上書き
      }
      case _ => sp
    }
    @tailrec
    def g(ves: Map[Vertex, Seq[Edge]], sp: ShortestPath): ShortestPath = ves.headOption match {
      case Some((v, es)) => g(ves.tail, h(v, es, sp))
      case _ => sp
    }
    @tailrec
    def f(sp: ShortestPath, i: Int = 0): ShortestPath = {
      if (i < graph.vertices.size) {
        val fr = g(graph.es, sp)
        if (fr == sp) fr else f(fr, i + 1)
      }
      else throw new Exception("負の閉炉がありました")
    }
    f(initPath)
  }

  case class Graph(es: Map[Vertex, Seq[Edge]]) {
    val vertices: Seq[Vertex] = es.toSeq.flatMap { case (v, es) => v +: es.map(_.v) }
  }

  case class Vertex(name: String)
  case class Edge(v: Vertex, weight: Weight)
  type Weight = Int
  type ShortestPath = Map[Vertex, Weight]

  /*
            C
          /   \
        A   -  B
      D   F
     C>A>B が負のループだと最小が更新され続けるので頂点数以上更新があった場合は、負のループだと分かる
   */
  def sampleGraph: Graph = Graph(
    Map(
      Vertex("C") -> Seq(Edge(Vertex("A"), 2), Edge(Vertex("B"), 1)),
      Vertex("A") -> Seq(Edge(Vertex("B"), 1), Edge(Vertex("D"), 1), Edge(Vertex("F"), 1)),
      Vertex("B") -> Seq(Edge(Vertex("C"), 6))
    )
  )
}