Dijkstra avec file de priorité

let dijkstra_tas adj depart n_aretes =
  let n = Array.length adj in
  let infini = 1_000_000 in
  let dist = Array.make n infini in
  let t = cree_c (n + n_aretes) in       (* capacité : assez de poussées *)
  dist.(depart) <- 0;
  insere_c t (0, depart);
  while t.taille > 0 do
    let (du, u) = extrait_min_c t in
    if du = dist.(u) then               (* ignorer les entrées périmées *)
      List.iter (fun (v, poids) ->
        if du + poids < dist.(v) then begin
          dist.(v) <- du + poids;
          insere_c t (dist.(v), v)       (* on pousse la nouvelle distance *)
        end
      ) adj.(u)
  done;
  dist

Au lieu de chercher le minimum en $\Theta (n)$, on l'extrait du tas en $\Theta (\log n)$. À chaque relâchement réussi, on pousse le couple (nouvelle_distance, v) ; une même destination peut être poussée plusieurs fois, d'où le test du = dist.(u) qui ignore les entrées périmées. Coût $\Theta ((n+m)\log n)$ — bien meilleur que le $\Theta (n^2)$ du chapitre 16 sur les graphes creux. (extrait_min_c est la version « couples » de extrait_min.)