Immutable implementation of Bellman-Ford single source shortest path

[shawjef3]

@jimka

Can I replace Edge[A] => Int and Map[A,Int] with something more general to allow the return values of the weight function to be anything which supports + and < ?

You could use A <: Number.

@jimka

2. The return value of bellmanFord is of type (Map[A, Int], Map[A, A]). I have to reuse this type several times within the algorithm on the local functions relax and relaxationPass. I’ve defined a type alias DP to reduce typing, but I suspect there’s a clearer way to do this.

When you move from mutable state to immutable, your state becomes parameters and return values. I don’t see a way around this.

@jimka

3. the local function relaxationPass is a tail recursive function whose goal is to reduce the given dp several times, i-1 times to be exact. Can’t I rewrite this somehow as call to some variant of fold/reduce which ignores its iteration variable?

I might have something along the lines of what you’re looking for.

Vertices.indices.reverse.dropRight(1).foldLeft((Map((source -> 0)), Map())) ...