Adloun

OCaml (option informatique) · Chapitre 16 · Application directe du cours

Graphe pondéré

Plus courts chemins : Dijkstra · niveau 1 (application)

Énoncé

Construire un graphe pondéré en listes d'adjacence (int * int) list array et écrire ajoute_arc adj u v poids.

Corrigé

let pondere_vide n = Array.make n []

let ajoute_arc adj u v poids = adj.(u) <- (v, poids) :: adj.(u)

let ajoute_arete adj u v poids =        (* non orienté *)
  adj.(u) <- (v, poids) :: adj.(u);
  adj.(v) <- (u, poids) :: adj.(v)

Chaque voisin est un couple (sommet, poids). C'est l'extension naturelle des listes d'adjacence du chapitre 14.

Exercices semblables

Le cours du chapitre · Tous les exercices du chapitre