ダイクストラ法
練習がてら、F#でダイクストラ法のアルゴリズムを実装してみた。といっても最短距離を求めるところまでで、最短経路は求めていない。
入力データはこのページにあるものをそのまま利用させてもらった。このページはわかりやすくてためになります。
プログラムではupdate関数の副作用を無くすために毎回配列をcopyしているので、その分メモリを食うはず。プログラムとしてはなんとか動作はするが、もうちょっとうまくかけそうな気がするなぁ。
#light "off" let pe x = print_any x;print_endline "";; //点の数 let nodenum = 6;; //(始点,終点,間のコスト) let adj = [|(0,1,5);(0,2,4);(0,3,2);(1,2,2);(1,4,6);(2,3,3);(2,5,2);(3,5,6);(4,5,4)|];; //i番目に始点から点iまでのコストと、点iが確定したかのflagを格納する配列 let cost = Array.init nodenum (fun x -> (int.MaxValue,false));; cost.[0] <- (0,false);; //1つの点を確定させる操作。確定後のコストを新しい配列で返す let update adj cost = //確定していない点の中で最小のものを求める let unchecked = Array.find (fun x -> snd x = false) cost in let next = Array.fold_left (fun acc x -> if not (snd x) then if (fst acc) > (fst x) then x else acc else acc) unchecked cost in let pos = Array.find_index ((=)next) cost in let ret = Array.copy cost in ret.[pos] <- (fst next,true); //確定した点からたどれる点のコストを更新 Array.iter (fun x -> let s,e,c = x in if s = pos then if fst ret.[e] > fst ret.[s] + c then ret.[e] <- (fst ret.[s] + c,snd ret.[e]) else () else if e = pos then if fst ret.[s] > fst ret.[e] + c then ret.[s] <- (fst ret.[e] + c,snd ret.[s]) else () else ()) adj; ret;; //全ての点が確定するまで確定操作を繰り返す Array.fold_left (fun acc _ -> let next = update adj acc in pe next;next) <| cost <| Array.zero_create nodenum |> ignore;;