let bellman_fordSP source weightedDirectedEdges (* [(from, to, weight)] *) = //BELLMAN-FORD algorithm to the shortest path //from pseudo code in Algortihms Unlocked, Thomas H. Cormen let vertices = weightedDirectedEdges |> List.collect (fun (u, v, _) -> [u; v]) |> List.distinct let n = vertices |> List.length let shortest = Array.zeroCreate n let pred = Array.zeroCreate n //relax procedure let relax u v w = //w == weight u v let dist = shortest.[u] + w if dist < shortest.[v] then shortest.[v] <- dist pred.[v] <- u let inf = System.Int32.MaxValue let nil = -1 //BELLMAN-FORD algorithm for i = 0 to n - 1 do shortest.[i] <- inf pred.[i] <- nil shortest.[source] <- 0 for i = 1 to n - 1 do for (u, v, w) in weightedDirectedEdges do relax u v w pred |> Array.mapi (fun i p -> (p, i, shortest.[i])) |> Array.filter (fun (x, _, _) -> x <> nil) |> Array.toList let s, t, x, y, z = 0, 1, 2, 3, 4 let translate i = match i with | 0 -> 's' | 1 -> 't' | 2 -> 'x' | 3 -> 'y' | 4 -> 'z' | _ -> failwith "invalid" let directedEdges = //u -> v : w == u, v, w [ (s, t, 6); (s, y, 4); (t, x, 3); (t, y, 2); (x, z, 4); (y, t, 1); (y, z, 3); (y, x, 9); (z, x, 5); (z, s, 7) ] let sp = directedEdges |> bellman_fordSP s sp |> printfn "%A" let f (u, v, t) = (translate u), (translate v) sp |> List.map f |> printfn "%A" let g (u, v, t) = string (translate u) + " -> " + string (translate v) sp |> List.map g |> printfn "%A" sp |> List.map g |> List.fold (fun acc x -> acc + x + "\n") "" |> printfn "%s" (* [(3, 1, 5); (1, 2, 8); (0, 3, 4); (3, 4, 7)] [('y', 't'); ('t', 'x'); ('s', 'y'); ('y', 'z')] ["y -> t"; "t -> x"; "s -> y"; "y -> z"] y -> t t -> x s -> y y -> z *)