Fiche de Révision : Algorithme de Dijkstra et Comparatif des Trois Algorithmes en OCaml

Introduction

L’algorithmique des graphes est un domaine fondamental en informatique, notamment pour résoudre des problèmes de plus court chemin, de parcours, et d’optimisation. Parmi les algorithmes les plus célèbres pour trouver le plus court chemin dans un graphe pondéré, l’algorithme de Dijkstra occupe une place centrale.

Cette fiche de révision présente une étude détaillée de l’algorithme de Dijkstra, suivi d’un comparatif entre trois algorithmes classiques de recherche de chemin en OCaml : Dijkstra, Bellman-Ford, et Floyd-Warshall.

1. Algorithme de Dijkstra

1.1. Contexte et Problématique

L’algorithme de Dijkstra permet de résoudre le problème du plus court chemin à partir d’un sommet source vers tous les autres sommets dans un graphe orienté ou non orienté, avec des poids non négatifs.

Problème formel :
Étant donné un graphe [Formule] avec un poids [Formule], trouver la distance minimale [Formule] entre un sommet source [Formule] et chaque sommet [Formule].

1.2. Principe de l’algorithme

• Initialiser une liste des distances [Formule] avec [Formule] et [Formule] pour [Formule].

• Maintenir un ensemble de sommets non visités.

• À chaque itération, sélectionner le sommet non visité [Formule] avec la plus petite distance estimée [Formule].

• Mettre à jour les distances des voisins [Formule] de [Formule] via la relaxation :

  [Formule mathématique]

• Répéter jusqu’à ce que tous les sommets soient visités ou que les distances ne puissent plus être améliorées.

1.3. Pseudocode

let dijkstra graph source =
  let dist = Array.make (Array.length graph) max_int in
  dist.(source) <- 0;
  let visited = Array.make (Array.length graph) false in

  for _ = 0 to (Array.length graph - 1) do
    (* Trouver le sommet u non visité avec la plus petite distance *)
    let u = ref (-1) in
    let min_dist = ref max_int in
    for i = 0 to (Array.length graph - 1) do
      if not visited.(i) && dist.(i) < !min_dist then (
        u := i;
        min_dist := dist.(i)
      )
    done;

    if !u = -1 then () else (
      visited.(!u) <- true;
      (* Relaxation *)
      List.iter (fun (v, w) ->
        if dist.(!u) <> max_int && dist.(!u) + w < dist.(v) then
          dist.(v) <- dist.(!u) + w
      ) graph.(!u)
    )
  done;
  dist

1.4. Complexité temporelle

• Sans structure de données avancée : [Formule] où [Formule] est le nombre de sommets.
• Avec un tas binaire (priority queue) : [Formule] où [Formule] est le nombre d’arêtes.

2. Les Trois Algorithmes de Plus Court Chemin en OCaml

Nous allons comparer les algorithmes suivants :

2.1. Algorithme de Bellman-Ford

• Permet de gérer des poids négatifs.
• Calcule les plus courts chemins à partir d’une source.
• Détecte la présence de cycles de poids négatifs.

Pseudocode OCaml simplifié

let bellman_ford graph source =
  let dist = Array.make (Array.length graph) max_int in
  dist.(source) <- 0;

  for _ = 1 to (Array.length graph - 1) do
    for u = 0 to (Array.length graph - 1) do
      List.iter (fun (v, w) ->
        if dist.(u) <> max_int && dist.(u) + w < dist.(v) then
          dist.(v) <- dist.(u) + w
      ) graph.(u)
    done
  done;

  (* Vérification des cycles négatifs *)
  let has_negative_cycle = ref false in
  for u = 0 to (Array.length graph - 1) do
    List.iter (fun (v, w) ->
      if dist.(u) <> max_int && dist.(u) + w < dist.(v) then
        has_negative_cycle := true
    ) graph.(u)
  done;

  if !has_negative_cycle then failwith "Cycle négatif détecté";
  dist

2.2. Algorithme de Floyd-Warshall

• Résout le problème du plus court chemin pour toutes les paires de sommets.
• Utilise une matrice d’adjacence.
• Fonctionne avec poids négatifs (sans cycle négatif).

Formule de récurrence

Pour tout [Formule],
[Formule mathématique]

où [Formule] est la distance minimale entre [Formule] et [Formule] en utilisant uniquement les sommets [Formule] à [Formule] comme intermédiaires.

Pseudocode OCaml simplifié

let floyd_warshall graph =
  let n = Array.length graph in
  let dist = Array.init n (fun i -> Array.init n (fun j -> if i = j then 0 else graph.(i).(j))) in

  for k = 0 to n - 1 do
    for i = 0 to n - 1 do
      for j = 0 to n - 1 do
        if dist.(i).(k) + dist.(k).(j) < dist.(i).(j) then
          dist.(i).(j) <- dist.(i).(k) + dist.(k).(j)
      done
    done
  done;
  dist

3. Comparatif des trois algorithmes

4. Exemple concret en OCaml : Dijkstra sur un graphe simple

Considérons le graphe suivant, représenté sous forme de liste d’adjacence :

let graph = [|
  [(1, 7); (2, 9); (5, 14)];
  [(0, 7); (2, 10); (3, 15)];
  [(0, 9); (1, 10); (3, 11); (5, 2)];
  [(1, 15); (2, 11); (4, 6)];
  [(3, 6); (5, 9)];
  [(0, 14); (2, 2); (4, 9)]
|]

Pour calculer les plus courts chemins depuis le sommet 0 :

let distances = dijkstra graph 0;;
Array.iteri (fun i d -> Printf.printf "Distance de 0 à %d : %d\n" i d) distances;;

Résultat attendu :

Distance de 0 à 0 : 0
Distance de 0 à 1 : 7
Distance de 0 à 2 : 9
Distance de 0 à 3 : 20
Distance de 0 à 4 : 20
Distance de 0 à 5 : 11

5. Diagramme Mermaid : Relations entre les algorithmes

[Diagramme]

6. Conclusion

L’algorithme de Dijkstra est un outil puissant et efficace pour résoudre le problème du plus court chemin dans les graphes à poids positifs. Cependant, selon la nature du graphe (présence de poids négatifs, nécessité de connaître tous les plus courts chemins), il est important de choisir l’algorithme adapté :

• Dijkstra pour graphes positifs et grands graphes clairsemés,
• Bellman-Ford pour gérer poids négatifs et détecter les cycles négatifs,
• Floyd-Warshall pour les graphes denses et calculs entre toutes paires.

En OCaml, ces algorithmes peuvent être implémentés de manière concise et fonctionnelle, offrant à la fois lisibilité et efficacité.

Citation importante :

"Choisir le bon algorithme est essentiel pour optimiser à la fois la complexité temporelle et la mémoire selon les contraintes du problème et la nature du graphe."

Annexes : Conseils pour la mise en œuvre en OCaml

• Utiliser des types adaptés : listes d’adjacence pour graphes clairsemés, matrices pour graphes denses.
• Privilégier les structures comme les Heap ou PriorityQueue pour améliorer la performance de Dijkstra.
• Toujours vérifier la présence de poids négatifs avant d’utiliser Dijkstra.
• Tester les implémentations sur des graphes simples pour valider les résultats.

Fin de la fiche de révision.