Dijkstra's algorithm

Dijkstra.scala

object Dijkstra {
  case class Edge[T](node: T, cost: Double)
  case class Path[T](nodes: List[T], cost: Double)

  type Graph[T] = Map[T, List[Edge[T]]]

  def dijkstra[T](graph: Graph[T], paths: List[Path[T]], dest: T, visited: Set[T]): Option[Path[T]] = {
    def unvisitedPaths(node: T, path: Path[T]): List[Path[T]] =
      graph(node).filterNot(edge => visited.contains(edge.node))
                 .map(edge => Path(edge.node +: path.nodes, path.cost + edge.cost))
    for {
      path <- paths.headOption
      node <- path.nodes.headOption
      result <- if (node == dest)
                  Some(Path(path.nodes.reverse, path.cost))
                else
                  dijkstra(graph, (unvisitedPaths(node, path) ++ paths.tail).sortBy(_.cost), dest, visited + node)
    } yield result
  }

  def main(args: Array[String]): Unit = {
    val graph: Graph[String] = Map(
      "a" -> List(Edge("b", 7.0), Edge("c", 9.0), Edge("f", 14.0)),
      "b" -> List(Edge("c", 10.0), Edge("d", 15.0)),
      "c" -> List(Edge("d", 11.0), Edge("f", 2.0)),
      "d" -> List(Edge("e", 6.0)),
      "e" -> List(Edge("f", 9.0)),
      "f" -> List.empty
    )

    val start = Path(List("a"), 0d)

    val result1 = dijkstra(graph, List(start), "e", Set.empty)
    println(result1)  // Some(Path(List(a, c, d, e),26.0))

    val result2 = dijkstra(graph, List(start), "z", Set.empty)
    println(result2)  // None
  }
}