1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
|
let M = [|[|112;91;193;0;0;0;0;0;0|];
[|0;0;107;0;0;0;0;0;0|];
[|0;0;0;80;0;0;0;0;0|];
[|107;0;0;0;217;109;0;0;0|];
[|0;80;0;0;117;219;0;0;0|];
[|0;0;217;117;0;126;159;200;0|];
[|0;0;109;219;126;0;65;128;0|];
[|0;0;0;0;159;65;0;114;121|];
[|0;0;0;0;200;128;114;0;101|]|];;
let distance_min vecteur =
let longueur = vect_length vecteur in
let rec comparer2 = fun
poids_min tronçon initial final when initial=longueur+1 -> tronçon
| poids_min tronçon initial final when final=longueur+1 -> comparer2 poids_min tronçon (initial+1) 0
| poids_min tronçon initial final -> let poids_tronçon= (M.(initial)).(final-1) in
let poids_chemin = poids_tronçon+snd(vecteur.(initial)) in
if fst(vecteur.(final))=final && fst(vecteur.(initial))<>initial && poids_tronçon<>0 &&( poids_chemin<poids_min or poids_min=0)
then comparer2 poids_chemin ((initial,final),poids_tronçon) initial (final+1)
else comparer2 poids_min tronçon initial (final+1)
in comparer2 0 ((0,0),0) 0 1;;
let dijkstra tableau =
let plus_court_chemin= ref([]) in
let longueur= (vect_length tableau) in
let vecteur= make_vect longueur (0,0) in vecteur.(0)<- (-1,0) ;
for indice= 1 to (longueur-1) do vecteur.(indice) <- (indice,0); done;
let dernier_sommet= ref(0) in
while !dernier_sommet<>longueur do
let plus_court_tronçon = distance_min vecteur in
let precedent,suivant = fst(plus_court_tronçon) in
vecteur.(suivant) <- (precedent,(snd(plus_court_tronçon)+snd(vecteur.(precedent))));
dernier_sommet:= suivant;
done;
let antecedent= ref(longueur-1) in
while !antecedent<>0 do
let nouvel_antecedent= fst(vecteur.(!antecedent)) in
plus_court_chemin:= (nouvel_antecedent::(!plus_court_chemin));antecedent:= nouvel_antecedent;
done;
(!plus_court_chemin,snd(vecteur.(longueur-1))) ;;
dijkstra M;; |
Partager