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 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72
| (* 1 ; 2 ; 3 ; 4 ; 5 *)
let mat = [|[| 0 ; 10 ; 6 ; -1 ; -1 |]; (* 1 *)
[| 0 ; 0 ; -1 ; 2 ; 4 |]; (* 2 *)
[| 0 ; 0 ; 0 ; 1 ; 7 |]; (* 3 *)
[| 0 ; 0 ; 0 ; 0 ; 9 |]; (* 4 *)
[| 0 ; 0 ; 0 ; 0 ; 0 |]|] (* 5 *)
;;
let poid n1 n2 =
if mat.(n1-1).(n2-1) <> 0 & n1<>n2 then mat.(n1-1).(n2-1)
else if n1<>n2 then mat.(n2-1).(n1-1)
else 0
;;
let poid_p mat_p n1 n2 =
mat_p.(n1-1).(n2-1);;
let rec minimum = function
| [x] , i -> x
| h::t ,i ->
match (poid i h) with
| 0 -> failwith "Le point de depart est dans provisoire!"
| _ -> if (poid i h) < (poid i (minimum (t,i))) then h
else (minimum (t,i));;
let rec remove_list x = function
| [] -> failwith "Rien a supprimer"
| h::t -> if h = x then t else h::(remove_list x t);;
let rec belong_list x = function
| [] -> false
| h::t -> if x = h then true else belong_list x t;;
let dijkstra mat =
(* Initialisation *)
let calcule = ref [1] in
let provisoires = ref [] in
let mat_p = ref mat in
for i = 2 to 5 do
if (poid 1 i) <> (-1) then provisoires := i::!provisoires;
done;
(*----------------*)
(* Itérations *)
while !provisoires <> [] do
let x = minimum !provisoires 1 in
calcule := x::!calcule;
provisoires := remove_list x !provisoires;
for y = 2 to 5 do
if (poid x y) <> (-1) & x<>y
then begin
if belong_list y !calcule then failwith "calcule"
else if belong_list y !provisoires
then begin
if (poid_p mat_p 1 x) + (poid x y) < (poid_p mat_p 1 y) then
!mat_p.(0).(y) <- (poid_p !mat_p 1 x) + (poid !mat_p x y)
end
else begin
provisoires := y::!provisoires;
!mat_p.(0).(y) <- (poid_p !mat_p 1 x) + (poid x y);
end
end;
done;
done;
!mat_p;
;; |
Partager