4 people like it.

# BELLMAN-FORD algorithm

BELLMAN-FORD algorithm to the shortest path based on pseudo code in Algortihms Unlocked

 ``` 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: 62: 63: ``` ``````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 *) ``````
val bellman_fordSP : source:int -> weightedDirectedEdges:(int * int * int) list -> (int * int * int) list

Full name: Script.bellman_fordSP
val source : int
val weightedDirectedEdges : (int * int * int) list
val vertices : int list
Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
| ( [] )
| ( :: ) of Head: 'T * Tail: 'T list
interface IEnumerable
interface IEnumerable<'T>
member GetSlice : startIndex:int option * endIndex:int option -> 'T list
member IsEmpty : bool
member Item : index:int -> 'T with get
member Length : int
member Tail : 'T list
static member Cons : head:'T * tail:'T list -> 'T list
static member Empty : 'T list

Full name: Microsoft.FSharp.Collections.List<_>
val collect : mapping:('T -> 'U list) -> list:'T list -> 'U list

Full name: Microsoft.FSharp.Collections.List.collect
val u : int
val v : int
val distinct : list:'T list -> 'T list (requires equality)

Full name: Microsoft.FSharp.Collections.List.distinct
val n : int
val length : list:'T list -> int

Full name: Microsoft.FSharp.Collections.List.length
val shortest : int []
module Array

from Microsoft.FSharp.Collections
val zeroCreate : count:int -> 'T []

Full name: Microsoft.FSharp.Collections.Array.zeroCreate
Multiple items
val int : value:'T -> int (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int

--------------------
type int = int32

Full name: Microsoft.FSharp.Core.int

--------------------
type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>
val pred : int []
val relax : (int -> int -> int -> unit)
val w : int
val dist : int
val inf : int
namespace System
type Int32 =
struct
member CompareTo : value:obj -> int + 1 overload
member Equals : obj:obj -> bool + 1 overload
member GetHashCode : unit -> int
member GetTypeCode : unit -> TypeCode
member ToString : unit -> string + 3 overloads
static val MaxValue : int
static val MinValue : int
static member Parse : s:string -> int + 3 overloads
static member TryParse : s:string * result:int -> bool + 1 overload
end

Full name: System.Int32
field int.MaxValue = 2147483647
val nil : int
val i : int
val mapi : mapping:(int -> 'T -> 'U) -> array:'T [] -> 'U []

Full name: Microsoft.FSharp.Collections.Array.mapi
val p : int
val filter : predicate:('T -> bool) -> array:'T [] -> 'T []

Full name: Microsoft.FSharp.Collections.Array.filter
val x : int
val toList : array:'T [] -> 'T list

Full name: Microsoft.FSharp.Collections.Array.toList
val s : int

Full name: Script.s
val t : int

Full name: Script.t
val x : int

Full name: Script.x
val y : int

Full name: Script.y
val z : int

Full name: Script.z
val translate : i:int -> char

Full name: Script.translate
val failwith : message:string -> 'T

Full name: Microsoft.FSharp.Core.Operators.failwith
val directedEdges : (int * int * int) list

Full name: Script.directedEdges
val sp : (int * int * int) list

Full name: Script.sp
val printfn : format:Printf.TextWriterFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.printfn
val f : u:int * v:int * t:'a -> char * char

Full name: Script.f
val t : 'a
val map : mapping:('T -> 'U) -> list:'T list -> 'U list

Full name: Microsoft.FSharp.Collections.List.map
val g : u:int * v:int * t:'a -> string

Full name: Script.g
Multiple items
val string : value:'T -> string

Full name: Microsoft.FSharp.Core.Operators.string

--------------------
type string = System.String

Full name: Microsoft.FSharp.Core.string
val fold : folder:('State -> 'T -> 'State) -> state:'State -> list:'T list -> 'State

Full name: Microsoft.FSharp.Collections.List.fold
val acc : string
val x : string