Dijkstra.fold

let dijkstra g s e =
  let n = Array.length g in
  let dist = Array.make n max_int in
  let q = ref PairSet.(empty |> add (0,s)) in
  dist.(s) <- 0;
  while not (PairSet.is_empty !q) do
    let (d, u) = PairSet.min_elt !q in
    q := PairSet.remove (d, u) !q;
    List.iter
      (fun (v, w) ->
        let newdist = dist.(u) + w in
        if newdist < dist.(v) then
        begin
          q := PairSet.add (newdist, v) !q;
          dist.(v) <- newdist
        end
      )
      g.(u)
  done;
  dist.(e)

type lexer =
  { line_count :: Int,
    lexbuf     :: LexBuf }

fun dijkstra g s e =>
  let n = Array.length g
  let dist = Array.make n max_int
  let q = ref PairSet.(empty |> add (0, s))
  dist[s] := 0;
  while not (PairSet.is_empty !q) do
    let (d, u) = PairSet.min_elt !q;
    q := PairSet.remove (d, u) !q;
    List.iter
      ((v, w) ->
        let newdist = dist[u] + w;
        if newdist < dist[v] then
          q := PairSet.add (newdist, v) !q;
          dist[v] := newdist
        end)
      g[u]
  end;
  dist[e]