Floyd-Warshall and path reconstruction.

floyd_warshall.jl

typealias Edge (Int,Int)
typealias Vertex Int

function floyd_warshall(V::Set{Vertex}, E::Set{Edge}, C::Dict{Edge,Real})
    n = length(V)
    A = fill(Inf, n, n)
    N = cell(n, n)

    for v in V
        A[i,i] = 0
    end

    for (u,v) in E
        A[u,v] = C[(u,v)]
        N[u,v] = v
    end

    for k = 1:n, i = 1:n, j = 1:n
        w = A[i,k] + A[k,j]

        if A[i,j] > w
            A[i,j] = w
            N[i,j] = N[i,k]
        end

        if i == j && A[i,j] < 0 
            error("Negative cost cycle")
        end
    end

    return A, N
end

function fw_path(N::Array, u::Vertex, v::Vertex)
    isdefined(N, u, v) || return []

    path = Vertex[u]
    while u != v
        u = N[u,v]
        push!(path, u)
    end

    return path
end