egison-5.0.0: sample/bellman-ford.egi

-- Bellman-Ford algorithm for shortest paths

-- initiate a distance graph
def A : Matrix Integer :=
  [|[|0, 19, 36, 66, 99, 65|]
  , [|19, 0, 25, 59, 64, 31|]
  , [|36, 25, 0, 84, 48, 28|]
  , [|66, 59, 84, 0, 59, 29|]
  , [|99, 64, 48, 59, 0, 9|]
  , [|65, 31, 28, 29, 9, 0|]|]

def G.* {Ord a} (t1: Matrix a) (t2: Matrix a) : Matrix a := withSymbols [i]
  reduce min (contract (t1~#_i + t2~i_#))

assertEqual "all-pairs shortest paths"
  (match iterate (\P -> G.* P A) A as list something with
    | _ ++ $P :: #P :: _ -> P)
  [|[|  0, 19, 36, 66, 59, 50 |]
  , [| 19,  0, 25, 59, 40, 31 |]
  , [| 36, 25,  0, 57, 37, 28 |]
  , [| 66, 59, 57,  0, 38, 29 |]
  , [| 59, 40, 37, 38,  0,  9 |]
  , [| 50, 31, 28, 29,  9,  0 |]|]