ダイクストラ法

練習がてら、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;;