Prépa Code Connexion Inscription

Écrire une fonction dijkstra : (int * int) list array -> int -> int -> int qui renvoie la distance du plus court chemin entre le sommet depart et le sommet arrivee dans un graphe orienté pondéré à poids positifs.

Représentation : le graphe est un tableau adj de type (int * int) list array (liste d'adjacence pondérée), où adj.(i) est la liste des paires (voisin, poids). Les sommets sont numérotés de 0 à n-1.

Par exemple, [| [(1, 1); (2, 4)]; [(2, 2)]; [] |] représente un graphe à 3 sommets avec les arêtes 0→1 (poids 1), 0→2 (poids 4), 1→2 (poids 2).

Si le départ et l'arrivée sont le même sommet, la distance est 0. Tous les poids sont positifs ou nuls.

Indication : on peut implémenter Dijkstra sans file de priorité en parcourant à chaque étape le tableau des distances pour trouver le sommet non visité de distance minimale (complexité $O(V^2)$).