• Si certaines variables ou fonctions ne sont "pas définies" : Unbound constructor, Unbound value... pensez à évaluer les cellules au dessus...
• Évaluer une cellule : Shift-Entrée ou Ctrl-Entrée
• Regardez aussi Aide > Raccourcis claviers ou la palette (Ctrl-Shift-p)
• Si OCaml a "planté" : Noyau > Redémarrer

type r_barre = Inf | V of int  (* On travaille avec des entiers ici, ou des flottants si on veut *)

type r_barre = Inf | V of int

Outils mathématiques

Remarque : on pourrait aussi travailler directement avec des ints et max_int par exemple ; mais ce serait moins dans l'esprit des sujets de concours...

let minimum a b =
    match a, b with
    | _, Inf -> a
    | Inf, b -> b
    | V(x), V(y) -> V(min x y)
  
let somme a b =
    match a, b with
    | _, Inf -> Inf
    | Inf, _ -> Inf
    | V(x), V(y) -> V(x+y)
    
let inferieur a b =
    match a, b with
    | _, Inf -> true
    | Inf, _ -> false
    | V(x), V(y) -> x < y

val minimum : r_barre -> r_barre -> r_barre = <fun>

val somme : r_barre -> r_barre -> r_barre = <fun>

val inferieur : r_barre -> r_barre -> bool = <fun>

Floyd-Warshall

type mat_adj = r_barre array array

let graphe_matrice :mat_adj = [|
    [|V 0; V 3; V 8; Inf; V 4|];
    [|Inf; V 0; Inf; V 1; V 7|];
    [|Inf; V 4; V 0; Inf; Inf|];
    [|V 2; Inf; V 5; V 0; Inf|];
    [|Inf; Inf; Inf; V 6; V 0|];
|]

type mat_adj = r_barre array array

val graphe_matrice : mat_adj =
  [|[|V 0; V 3; V 8; Inf; V 4|]; [|Inf; V 0; Inf; V 1; V 7|];
    [|Inf; V 4; V 0; Inf; Inf|]; [|V 2; Inf; V 5; V 0; Inf|];
    [|Inf; Inf; Inf; V 6; V 0|]|]

(* Ne surtout pas faire : Array.make n (Array.make n Inf), ou vous aurez des surprises*)
let matrice_vide n = Array.make_matrix n n Inf;;

matrice_vide 2

val matrice_vide : int -> r_barre array array = <fun>

- : r_barre array array = [|[|Inf; Inf|]; [|Inf; Inf|]|]

let copie_matrice mat =
    let n = Array.length mat in
    let copie = matrice_vide n in
    for i = 0 to n-1 do
        for j = 0 to n-1 do
            copie.(i).(j) <- mat.(i).(j)
        done
    done;
    copie

val copie_matrice : r_barre array array -> r_barre array array = <fun>

let floyd_warshall graphe =
    let d = copie_matrice graphe and n = Array.length graphe in
    for k = 0 to n-1 do
        for i = 0 to n-1 do
            for j = 0 to n-1 do
                d.(i).(j) <- minimum d.(i).(j) (somme d.(i).(k) d.(k).(j))
            done
        done
    done;
    d;;

floyd_warshall graphe_matrice

val floyd_warshall : r_barre array array -> r_barre array array = <fun>

- : r_barre array array =
[|[|V 0; V 3; V 8; V 4; V 4|]; [|V 3; V 0; V 6; V 1; V 7|];
  [|V 7; V 4; V 0; V 5; V 11|]; [|V 2; V 5; V 5; V 0; V 6|];
  [|V 8; V 11; V 11; V 6; V 0|]|]

Dijkstra

type distance = r_barre and sommet = int;;
type liste_adj = (sommet * distance) list array;;

let graphe_liste :liste_adj = [|
    [(1, V 3); (2, V 8); (4, V 4)];
    [(3, V 1); (4, V 7)];
    [(1, V 4)];
    [(0, V 2); (2, V 5)];
    [(3, V 6)];
|]

type distance = r_barre
and sommet = int

type liste_adj = (sommet * distance) list array

val graphe_liste : liste_adj =
  [|[(1, V 3); (2, V 8); (4, V 4)]; [(3, V 1); (4, V 7)]; [(1, V 4)];
    [(0, V 2); (2, V 5)]; [(3, V 6)]|]

• File de priorité qui contient des couples (distance, sommet).
• Pour créer une file de priorité, il y a de nombreuses méthodes. On utilise ici : https://ocaml.org/learn/tutorials/set.fr.html
• Pas du tout à connaître pour les concours
• Attention : c'est une structure fonctionnelle pure / non mutable donc les différentes opérations renvoient une nouvelle file de priorité et ne modifient pas l'original.

module Fprio = Set.Make(struct type t = distance * sommet let compare = compare end)

module Fprio :
  sig
    type elt = distance * sommet
    type t
    val empty : t
    val is_empty : t -> bool
    val mem : elt -> t -> bool
    val add : elt -> t -> t
    val singleton : elt -> t
    val remove : elt -> t -> t
    val union : t -> t -> t
    val inter : t -> t -> t
    val diff : t -> t -> t
    val compare : t -> t -> int
    val equal : t -> t -> bool
    val subset : t -> t -> bool
    val iter : (elt -> unit) -> t -> unit
    val map : (elt -> elt) -> t -> t
    val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a
    val for_all : (elt -> bool) -> t -> bool
    val exists : (elt -> bool) -> t -> bool
    val filter : (elt -> bool) -> t -> t
    val partition : (elt -> bool) -> t -> t * t
    val cardinal : t -> int
    val elements : t -> elt list
    val min_elt : t -> elt
    val min_elt_opt : t -> elt option
    val max_elt : t -> elt
    val max_elt_opt : t -> elt option
    val choose : t -> elt
    val choose_opt : t -> elt option
    val split : elt -> t -> t * bool * t
    val find : elt -> t -> elt
    val find_opt : elt -> t -> elt option
    val find_first : (elt -> bool) -> t -> elt
    val find_first_opt : (elt -> bool) -> t -> elt option
    val find_last : (elt -> bool) -> t -> elt
    val find_last_opt : (elt -> bool) -> t -> elt option
    val of_list : elt list -> t
  end

(* Structure de donnée non mutable *)
Fprio.singleton (V 0, 0)

- : Fprio.t = <abstr>

List.iter

- : ('a -> unit) -> 'a list -> unit = <fun>

(* On peut écrire quasiment le même code qu'en Python avec deux boucles for imbriquées
si on manipule un `... array array`. C'est possible... *)

let list_adj_to_mat_adj graphe =
    Array.init (Array.length graphe) (fun i -> Array.of_list graphe.(i));;

list_adj_to_mat_adj graphe_liste

val list_adj_to_mat_adj : 'a list array -> 'a array array = <fun>

- : (sommet * distance) array array =
[|[|(1, V 3); (2, V 8); (4, V 4)|]; [|(3, V 1); (4, V 7)|]; [|(1, V 4)|];
  [|(0, V 2); (2, V 5)|]; [|(3, V 6)|]|]

(* Avec des références, c'est moche *)

let dijkstra_ref voisins source =
  let fileprio = ref Fprio.empty and d = Array.make (Array.length voisins) Inf in
  d.(source) <- V 0;
  fileprio := Fprio.add (V 0, source) !fileprio;
  while not (Fprio.is_empty !fileprio) do
      let (du, u) = Fprio.min_elt !fileprio in    (* ne modifie PAS fileprio *)
      fileprio := Fprio.remove (du, u) !fileprio;
      List.iter
          (fun (v, dist) -> let nouvelle = somme d.(u) dist in
              if inferieur nouvelle d.(v) then    (* Attention, pas < *)
                  begin
                  d.(v) <- nouvelle;
                  fileprio := Fprio.add (nouvelle, v) !fileprio
                  end
          )
          voisins.(u)
  done;
  d

val dijkstra_ref : (sommet * r_barre) list array -> sommet -> r_barre array =
  <fun>

dijkstra_ref graphe_liste 0

- : r_barre array = [|V 0; V 3; V 8; V 4; V 4|]

List.fold_left

- : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a = <fun>

let dijkstra voisins source =
    let d = Array.make (Array.length voisins) Inf in
    d.(source) <- V 0;
    let rec parcours fileprio =
        if Fprio.is_empty fileprio then d
        else begin
            let (du, u) = Fprio.min_elt fileprio in
            let nouvelle_fileprio = Fprio.remove (du, u) fileprio in
            let mise_a_jour file (v, dist) = 
                let nouvelle = somme d.(u) dist in
                    if inferieur nouvelle d.(v) then
                        begin
                        d.(v) <- nouvelle;           (* modifie d *)
                        Fprio.add (nouvelle, v) file
                        end
                    else
                        file
            in parcours (List.fold_left mise_a_jour nouvelle_fileprio voisins.(u))
        end
    in parcours (Fprio.singleton (V 0, source))

val dijkstra : (sommet * r_barre) list array -> sommet -> r_barre array =
  <fun>

dijkstra graphe_liste 0

- : r_barre array = [|V 0; V 3; V 8; V 4; V 4|]