30 lines
1.0 KiB
Scala
30 lines
1.0 KiB
Scala
object Dijkstra {
|
|
|
|
type Path[Key] = (Double, List[Key])
|
|
|
|
def Dijkstra[Key](lookup: Map[Key, List[(Double, Key)]], fringe: List[Path[Key]], dest: Key, visited: Set[Key]): Path[Key] = fringe match {
|
|
case (dist, path) :: fringe_rest => path match {case key :: path_rest =>
|
|
if (key == dest) (dist, path.reverse)
|
|
else {
|
|
val paths = lookup(key).flatMap {case (d, key) => if (!visited.contains(key)) List((dist + d, key :: path)) else Nil}
|
|
val sorted_fringe = (paths ++ fringe_rest).sortWith {case ((d1, _), (d2, _)) => d1 < d2}
|
|
Dijkstra(lookup, sorted_fringe, dest, visited + key)
|
|
}
|
|
}
|
|
case Nil => (0, List())
|
|
}
|
|
|
|
def main(x: Array[String]): Unit = {
|
|
val lookup = Map(
|
|
"a" -> List((7.0, "b"), (9.0, "c"), (14.0, "f")),
|
|
"b" -> List((10.0, "c"), (15.0, "d")),
|
|
"c" -> List((11.0, "d"), (2.0, "f")),
|
|
"d" -> List((6.0, "e")),
|
|
"e" -> List((9.0, "f")),
|
|
"f" -> Nil
|
|
)
|
|
val res = Dijkstra[String](lookup, List((0, List("a"))), "e", Set())
|
|
println(res)
|
|
}
|
|
}
|