(* Dijkstra *)

let select_best sommet cible liste_aretes=
  let rec better=function
    | [] -> max_int
    | (dep,pds,arr)::reste -> let d=better reste in
	if ( ((dep<>sommet)||(arr<>cible)) && ((arr<>sommet)||(dep<>cible)) )
	  || (d<=pds)
	then d else pds
  in better liste_aretes;;
(*select_best : 'a -> 'a -> ('a * int * 'a) list -> int = <fun>*)

let rec initialisation_c2 depart aretes=function
  | [] -> []
  | s::reste -> if s=depart
    then initialisation_c2 depart aretes reste
    else (s,select_best s depart aretes,depart)::(initialisation_c2 depart aretes reste);;

(*initialisation_c2 :
 'a -> ('a * int * 'a) list -> 'a list -> ('a * int * 'a) list = <fun>*)



let  sommets_ex=["A";"B";"C";"D";"E";"F";"G"]
and aretes_ex=["A",1,"B";"A",2,"D";"B",10,"E";"B",3,"C";"D",7,"C";"D",100,"G";
	       "C",15,"F";"E",4,"F";"E",20,"G";"F",8,"G"];;

initialisation_c2 "C" aretes_ex sommets_ex;;

(*- : (string * int * string) list =
 ["A", 1073741823, "C"; "B", 3, "C"; "D", 7, "C"; "E", 1073741823, "C";
  "F", 15, "C"; "G", 1073741823, "C"] *)



let selectionner c2=
  let rec mini=function
    | [] -> failwith "Abruti"
    | [s,d,p]->s,d,p
    | (s,d,p)::reste->let s_m,m,p_m=mini reste in
	if d<m then s,d,p else s_m,m,p_m 
  in mini c2;;
(* selectionner : ('a * 'b * 'c) list -> 'a * 'b * 'c = <fun> *)

selectionner (initialisation_c2 "G" aretes_ex sommets_ex);;
(*- : string * int * string = "F", 8, "G" *)


let rec maj_c2 s dist ar=function
  | [] -> []
  | (t,_,_)::reste when t=s -> maj_c2 s dist ar reste
  | (t,d,p)::reste -> let d2=select_best t s ar in
      if (d2<>max_int) && (dist+d2<d)  (* Mouais... *)
      then (t,dist+d2,s)::(maj_c2 s dist ar reste) 
      else (t,d,p)::(maj_c2 s dist ar reste);;

(*maj_c2 :
 'a ->
 int -> ('a * 'a * int) list -> ('a * int * 'a) list -> ('a * int * 'a) list =
 <fun>*)

let rec mon_assoc x=function
  | [] -> failwith "tss..."
  | (y,d,z)::reste when y=x ->d,z
  | (y,_,_)::reste -> mon_assoc x reste;; 


let rec reconstruire depart arrivee c1=
  if arrivee=depart then [depart]
  else let _,etape=mon_assoc arrivee c1 in
    arrivee::(reconstruire depart etape c1);;


exception Fini;;

let dikstra depart arrivee sommets aretes=
  let c1=ref [depart,0,depart] and c2=ref (initialisation_c2 depart aretes sommets)
  in try
      for i=1 to list_length sommets 
      do let s,d,p= selectionner !c2 in
	c1:=(s,d,p)::!c1;
	c2:=maj_c2 s d  aretes !c2;
	if s=arrivee  then raise Fini
      done;
      0,reconstruire depart arrivee !c1 (* n'arrive pas *)
    with Fini -> fst (mon_assoc arrivee !c1),rev (reconstruire depart arrivee !c1);;
(*dikstra :
 'a ->
 'a ->
 'a list ->
 ('a * int * 'a) list -> ('a * int * 'a) list * ('a * int * 'a) list = <fun>*)

dikstra "A" "G" sommets_ex aretes_ex;;