Dijkstra-like routing algorithm
There are a few things how this could be improved.



First, a few minor quibbles about syntax:


When using a type annotation, do not put a space before the : – name: Type, please. (source)
In a chain of higher-order methods, do not use the . to invoke the method. For example this

val tentative = edges.flatMap(e =&gt; Set(e.from, e.to)).map(n =&gt; (n, if (n.value == start)  Some(List.empty[Edge[T]]) else None )).toMap


should be

val tentative = edges flatMap (e =&gt; Set(e.from, e.to)) map (n =&gt; (n, if (n.value == start) Some(List.empty[Edge[T]]) else None)).toMap


(source)
When a chain of transformations is very long, splitting inside the lambdas can be an acceptable solution:

val tentative = edges flatMap (
    e =&gt; Set(e.from, e.to)
  ) map (n =&gt;
    (n, if (n.value == start) Some(List.empty[Edge[T]]) else None)
  ).toMap

yield { block } is “evil” and should be avoided. for-comprehensions can be rewritten less clearly with flatMap and filter, but this may actually be preferable when the transformations are deeply nested.


Now let's look at this piece of your code:

for(edge &lt;- fromHere if tentative.contains(edge.to)) yield {
  tentative.get(edge.to) match {
    case None =&gt; throw new Error("broken algorithm")
    case Some(Some(knownroute)) if (knownroute.map(_.dist).sum &lt; route.map(_.dist).sum + edge.dist) =&gt; (edge.to, Some(knownroute))
    case _ =&gt;(edge.to, Some(edge :: route))
  }
}


As I said, this could be rewritten to avoid the comprehension.

fromHere filter (edge =&gt; tentative.contains(edge.to)) flatMap { edge =&gt;
  tentative.get(edge.to) match {
    case None =&gt; throw new Error("broken algorithm")
    case Some(Some(knownroute)) if (knownroute.map(_.dist).sum &lt; route.map(_.dist).sum + edge.dist) =&gt; (edge.to, Some(knownroute))
    case _ =&gt; (edge.to, Some(edge :: route))
  }
}


The tentative.get(…) returns an Option, which will be None if no element for that key was found. But that means we can get rid of the filter! Instead, we map over the result of the get, which removes one level of Options:

fromHere flatMap { edge =&gt;
  tentative.get(edge.to) map {
    case Some(knownroute) if (knownroute.map(_.dist).sum &lt; route.map(_.dist).sum + edge.dist) =&gt; (edge.to, Some(knownroute))
    case _ =&gt; (edge.to, Some(edge :: route))
  }
}


Destructuring the Option with Pattern matching is a bit tedious. Actually, we want to do one thing, orElse some default case.

fromHere flatMap { edge =&gt;
  tentative.get(edge.to) map { maybeRoute =&gt;
    maybeRoute filter (knownroute =&gt;
      knownroute.map(_.dist).sum &lt; route.map(_.dist).sum + edge.dist
    ) map (knownroute =&gt;
      Pair(edge.to, Some(knownroute)
    ) getOrElse (Pair(edge.to, Some(edge :: route)))
  }
}


But this is an unreadable mess! Yes, it somehow is. We can improve this by adding a Route class, e.g:

case class Route[T](route: List[Edge[T]], dist: Int) {
  val length = route.length

  def this(route: List[Edge[T]]) = this(route, route map (_.dist) sum)

  def this() = this(List.empty[Edge[T]], 0)

  def ::(edge: Edge[T]) = Route(edge :: route, dist + edge.dist)
}

val tentative: Map[Node[T], Option[Route[T]] = ...


The main advantage is that this keeps track of a route's distance, which means the above code becomes the slightly more accessible

fromHere flatMap { edge =&gt;
  tentative.get(edge.to) map { maybeRoute =&gt;
    val maybeBetterRoute =
      maybeRoute filter (knownRoute =&gt; knownRoute.dist &lt; route.dist + edge.dist)
    maybeBetterRoute map (knownRoute =&gt;
      Pair(edge.to, Some(knownroute)
    ) getOrElse (
      Pair(edge.to, Some(edge :: route))
    )
  }
}


You calculate the fromHere each time, which is an O(n) calculation, I think:

val fromHere = edges.filter(e =&gt; e.from == node)


It may be better to build a Map[Node[T], List[Edge[T]]] before the recursion, which is also a fairly cheap operation:

val edgesBySource = edges groupBy (_.from)


then: val fromHere = edgesBySource.get(node).flatten. I assume this would pay off soon for non-tiny graphs.