113 lines
3.4 KiB
OCaml
113 lines
3.4 KiB
OCaml
|
let ii = infinity;;
|
|||
|
|
|
|||
|
|
let g = [|
|
|||
|
|
(* 0 1 2 3 4 5 6 7 8 9 10*)
|
|||
|
|
(*0*) [|0.;1.;2.;ii;ii;ii;ii;ii;ii;ii;ii|];
|
|||
|
|
(*1*) [|ii;0.;ii;1.;ii;ii;ii;ii;ii;ii;ii|];
|
|||
|
|
(*2*) [|ii;ii;0.;3.;2.;ii;ii;ii;ii;ii;ii|];
|
|||
|
|
(*3*) [|ii;ii;ii;0.;ii;4.;1.;ii;ii;ii;ii|];
|
|||
|
|
(*4*) [|ii;ii;ii;ii;0.;ii;2.;ii;ii;ii;ii|];
|
|||
|
|
(*5*) [|ii;1.;ii;ii;ii;0.;ii;ii;ii;ii;ii|];
|
|||
|
|
(*6*) [|ii;ii;ii;ii;ii;ii;0.;ii;ii;3.;ii|];
|
|||
|
|
(*7*) [|ii;ii;ii;ii;ii;ii;4.;0.;ii;ii;ii|];
|
|||
|
|
(*8*) [|ii;ii;ii;ii;ii;ii;ii;1.;0.;ii;ii|];
|
|||
|
|
(*9*) [|ii;ii;ii;ii;ii;ii;ii;ii;ii;0.;3.|];
|
|||
|
|
(*10*)[|9.;ii;ii;ii;ii;ii;ii;ii;8.;ii;0.|];|];;
|
|||
|
|
|
|||
|
|
let copie_matrice m =
|
|||
|
|
let p = Array.length m and q = Array.length m.(0) in
|
|||
|
|
let c = Array.make_matrix p q m.(0).(0) in
|
|||
|
|
for i = 0 to p-1 do
|
|||
|
|
for j = 0 to q-1 do
|
|||
|
|
c.(i).(j) <- m.(i).(j)
|
|||
|
|
done;
|
|||
|
|
done;
|
|||
|
|
c;;
|
|||
|
|
|
|||
|
|
let ecraser_matrice m1 m2 =
|
|||
|
|
let p = Array.length m2 and q = Array.length m2.(0) in
|
|||
|
|
for i = 0 to p-1 do
|
|||
|
|
for j = 0 to q-1 do
|
|||
|
|
m1.(i).(j) <- m2.(i).(j)
|
|||
|
|
done;
|
|||
|
|
done;;
|
|||
|
|
|
|||
|
|
let floyd_warshall g =
|
|||
|
|
let n = Array.length g in
|
|||
|
|
(* w^(k) pour k=-1 *)
|
|||
|
|
let w = copie_matrice g in
|
|||
|
|
for k = 0 to n-1 do
|
|||
|
|
(* mise <20> jour de w^(k) *)
|
|||
|
|
let c = Array.make_matrix n n 0. in
|
|||
|
|
for i = 0 to n-1 do
|
|||
|
|
for j = 0 to n-1 do
|
|||
|
|
c.(i).(j) <- min w.(i).(j) (w.(i).(k)+.w.(k).(j))
|
|||
|
|
done;
|
|||
|
|
done;
|
|||
|
|
ecraser_matrice w c;
|
|||
|
|
done;
|
|||
|
|
(* on retourne w^(n-1) *)
|
|||
|
|
w;;
|
|||
|
|
|
|||
|
|
|
|||
|
|
let transfo_matrice m =
|
|||
|
|
let p = Array.length m and q = Array.length m.(0) in
|
|||
|
|
let c = Array.make_matrix p q (m.(0).(0),[[(0,0)]]) in
|
|||
|
|
for i = 0 to p-1 do
|
|||
|
|
for j = 0 to q-1 do
|
|||
|
|
c.(i).(j) <- (m.(i).(j), [[(i,j)]])
|
|||
|
|
done;
|
|||
|
|
done;
|
|||
|
|
c;;
|
|||
|
|
|
|||
|
|
let rec joindre_chemins l1 l2 =
|
|||
|
|
let rec aux chemin li = match li with
|
|||
|
|
| [] -> []
|
|||
|
|
| h::t -> (chemin@h)::(aux chemin t) in
|
|||
|
|
match l1 with
|
|||
|
|
| [] -> []
|
|||
|
|
| h::t -> (aux h l2)@(joindre_chemins t l2);;
|
|||
|
|
|
|||
|
|
let floyd_warshall_complet g =
|
|||
|
|
let n = Array.length g in
|
|||
|
|
(* w^(k) pour k=-1 *)
|
|||
|
|
let w = transfo_matrice g in
|
|||
|
|
for k = 0 to n-1 do
|
|||
|
|
(* mise <20> jour de w^(k) *)
|
|||
|
|
let c = Array.make_matrix n n w.(0).(0) in
|
|||
|
|
for i = 0 to n-1 do
|
|||
|
|
for j = 0 to n-1 do
|
|||
|
|
let ((db,cb), (ds,cs), (dt,ct)) = (w.(i).(j), w.(i).(k), w.(k).(j)) in
|
|||
|
|
if db = ds +. dt then
|
|||
|
|
if db <> infinity then
|
|||
|
|
c.(i).(j) <- (db,cb@(joindre_chemins cs ct))
|
|||
|
|
else
|
|||
|
|
c.(i).(j) <- (db, cb)
|
|||
|
|
else if db > ds +. dt then
|
|||
|
|
c.(i).(j) <- (ds +. dt, joindre_chemins cs ct)
|
|||
|
|
else
|
|||
|
|
c.(i).(j) <- (db, cb);
|
|||
|
|
done;
|
|||
|
|
done;
|
|||
|
|
ecraser_matrice w c;
|
|||
|
|
done;
|
|||
|
|
(* on retourne w^(n-1) *)
|
|||
|
|
w;;
|
|||
|
|
|
|||
|
|
open Format;;
|
|||
|
|
let tous_les_chemins g =
|
|||
|
|
let mat = floyd_warshall_complet g in
|
|||
|
|
|
|||
|
|
let rec affiche_chemin last l = match l with
|
|||
|
|
| [] -> printf "%d\n" last
|
|||
|
|
| (i,j)::t -> (printf "%d -> " i); affiche_chemin j t in
|
|||
|
|
|
|||
|
|
for i = 0 to Array.length mat - 1 do
|
|||
|
|
for j = 0 to Array.length mat.(0) -1 do
|
|||
|
|
if i<>j then
|
|||
|
|
let (d,c) = mat.(i).(j) in printf "%d -> %d en %F :\n" i j d; List.iter (fun li -> printf " "; affiche_chemin j li) c;
|
|||
|
|
print_newline ()
|
|||
|
|
done
|
|||
|
|
done;;
|
|||
|
|
tous_les_chemins g;;
|