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<int> n
    let pred = Array.zeroCreate<int> 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 Head : 'T
  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

Raw view Test code New version

More information

Link:	http://fssnip.net/7Pw
Posted:	8 years ago
Author:	Fabio Galuppo
Tags:	array , list , tuple , shortest path