I’m implementing the Floyd-Warshall multiple-source shortest path algorithm in Scala. I haven’t debugged it yet, so don’t copy my code and expect it to work.

Nevertheless, there are a couple of things I find exceedingly ugly in my implementation, but don’t know of a better way of doing them. Maybe someone can give me some advice???

The algorithm starts with a structure describing the graph: `adj:Map[A,Set[A]]`

which specifies that any node of type `A`

connects to zero or more other nodes of the same type `A`

.

The function, `computeDistancePredecessors`

, computes two things. 1) `d`

, a *distance* map, which maps each pair `(x,y)`

of vertices to the integer distance from `x`

to `y`

. and 2) `pred`

, a *predecessor* map, which maps each pair `(x,y)`

of vertices to the vertex which is the predecessor of `y`

along the shortest path from `x`

to `y`

.

Two things that are ugly (in my opinion).

- I’m modeling infinite distance as simply pairs missing from the Map. This has ugly consequences.

`val d`

is effectively an initial value of a 2x2 matrix, implemented as a `Map[(A,A),Int]`

. If vertex `x`

is adjacent to vertex `y`

in the graph, then `d(x -> y)`

is the integer distance from `x`

to `y`

, and `d(x -> x) = 0`

for all vertices. In my implementation, if `x`

and `y`

are not adjacent, then `d.get(x->y) = None`

.

Many implementations of Floyd-Marshall use a special value for INFINITY, which as I understand Scala `Int`

does not support. This special value works with assignment, and `+`

and `<`

etc in intuitive ways. e.g., INFINITY + x = INFINITY for all x.

My implementation is ugly because I have 5 cases, each one representing the situation that a different distance is INFINITY. The classic Floyd-Marshall reduces these 5 cases to just 2 cases.

- I am using two concentric
`flatMap`

calls to immutably derive the next`d`

iteration from the current`d`

. There is one iteration per value of`k`

which is realized in my code as a`adj.foldLeft(d)(loop)`

.

The ugly thing is that I also need to derive a new value of `pred`

on each call to `loop`

. So I compute this `pred = pred + ((row -> col) -> pred(k -> col))`

which modifies the value of the free `var`

.

I don’t know how to do this better, as I don’t know how to make two concentric calls to `flatMap`

take a pair of `Map`

s and construct a new pair of maps, whereas normally `flatMap`

of `flatMap`

takes a `Map`

and contracts a new `Map`

.

There is a 3rd small issue described elsewhere which discusses the problem that concentric calls to `flatMap`

unfortunately cannot be abbreviated using the `for`

construct.

```
object FloydWarshall {
type ADJ[A] = Map[A,Set[A]]
def computeDistancePredecessors[A](adj:ADJ[A], source: A)(weight: Edge[A] => Int): (Map[(A,A),Int],Map[(A,A),A]) = {
val d: Map[(A, A), Int] = for {(src, dsts) <- adj
dst <- dsts + src
} yield (src -> dst) -> (if (src==dst) 0 else weight(Edge(src, dst)))
var pred: Map[(A, A), A] = for {(src, dsts) <- adj
dst <- dsts
} yield (src, dst) -> src
def loop(d: Map[(A, A), Int], k:A): Map[(A, A), Int] = {
val emptyMap: Map[(A, A), Int] = Map()
adj.flatMap { case (row, _) =>
adj.flatMap { case (col, _) =>
if (d.get(row -> col).isEmpty) {
if (d.get(row -> k).nonEmpty && d.get(k -> col).nonEmpty) {
pred = pred + ((row -> col) -> pred(k -> col)) // affecting the free var pred
Map((row -> col) -> (d(row -> k) + d(k -> col)))
} else { // either row->k or k->col is INFINITY
emptyMap
}
}
else { // d(row -> col) is empty, distance is INFINITY
if (d.get(row -> k).isEmpty || d.get(k -> col).isEmpty) { // either row->k or k->col is INFINITY
Map((row -> col) -> d(row -> col))
} else if (d(row -> k) + d(k -> col) < d(row -> col)) {
pred = pred + ((row -> col) -> pred(k -> col)) // affecting the free var pred
Map((row -> col) -> (d(row -> k) + d(k -> col)))
} else {
Map((row -> col) -> d(row -> col))
}
}
}
}
}
(adj.keys.foldLeft(d)(loop),pred)
}
def shortestPath[A](adj: ADJ[A], src: A, dst: A)(weight: Edge[A] => Int): Option[List[A]] = {
???
}
}
```