Implementar uma versão preguiçosa do algoritmo de Dijkstra.

Implementar uma versão preguiçosa do algoritmo de Dijkstra utilizando a linguagem Scala.
Considere as seguintes classes, utilizadas para representar um digrafo ponderado:

case class Arc[V] (tail: V, head: V, weight: Int)

class Digraph[V] private (out: Map[V, List[Arc[V] ] ] = Map[V, List[Arc[V] ] ] ( ) ) {
def +(t: (V, V, Int) ): Digraph[V] = {
val (x, y, w) = t
new Digraph[V] (out + ( (x → (Arc[V] (x, y, w)::out.getOrElse(x, Nil) ) ),
(y → out.getOrElse(y, Nil) ) ) )
}

def size: Int = out.size

override def toString = out.toString
}

object Digraph {
def apply[V] = new Digraph[V] ( )
}

Como de costume, seja D = (V, A) um digrafo e ω : A → N uma função custo que associa a cada arco a ∈ A um custo ω(a). Lembre-se que ∗a denota a ponta inicial de a e a∗ denota a ponta final de a. O processamento do algoritmo é sumarizado numa função step(d, C) que recebe d : X → N tal que d(x) é o custo de um sx-caminho ω-mínimo e C ⊇ ~δX e que consiste em:

Caso 1 C = ∅.
Neste caso, devolva d.

Caso 2 C 6= ∅. Neste caso, selecione a ∈ C tal que α = d(∗a) + ω(a) é mínimo. Há dois casos a considerar:

1 Caso 2.1 a∗ ∈ X.
Neste caso, devolva step(d, C \ {a}).

Caso 2.2 a∗ ∈/ X. Neste caso, devolva step(d ∪ {(a∗, α)}, C ∪ ~δ(a∗)).

A chamada inicial que produzirá os custos dos caminhos mínimos é step({(s, 0)}, ~δs). Implemente este algoritmo em Scala.