type node = Some of int | None
type graph = (node * float * node ) list

let graph = [(0, 0.5, 1); (1, 0.2, 3); (1, 0.8, 4); (2, 0.4, 4)]

let nodes g = List.sort_uniq (fun a b-> if a=b then 0 else if a < b then -1 else 1)
    (List.fold_left (fun out (a,b,c) -> a::c::out) [] g)

(*returns an assoc list with (node, (distanceToSource, predecessor)) predecessor = -1 if its not known*)
let init source =
  let n = nodes graph in
  let dist_pred_list = List.fold_right (fun (x:int) out-> if x<>source then (infinity,None)::out else (0.0,None)::out) n [] in
  List.combine n dist_pred_list

let rec run graph count infolist =
  if count >= 0 then
    List.fold_right (fun (u,w,v) out ->
        let u_info = (List.assoc u infolist) in
        let v_info = (List.assoc v infolist) in
        if (fst u_info) +. w < fst v_info then
        (v,((fst u_info) +. w,u))::out else out
      ) graph [] in
  run graph (count-1) infolist