ダイクストラ法を実装しようとしたら、よくわからないものになった

OCaml 30分プログラム

30分プログラム、その518。ダイクスラ法を実装しようとしたら、よくわからないものになった。

変な点は、対象とするグラフがDAGのみになっている点と、たぶん計算量が増えてる点。もともと手続き的だったアルゴリズムを、再帰でキレイに書こうして失敗したのが原因だと思う。

使い方

let nodes =
  ["A";"B";"C"]

let edges = [
  {from="A"; to_="B";cost=3};
  {from="B"; to_="C";cost=3};
  {from="A"; to_="C";cost=4};
]

let graph = {
  nodes = nodes;
  edges = edges;
}

let main () =
  short_path graph "A" "C"

ソースコード

let (@@) f g = f g
let (+>) f g = g f

type node = string
type edge = {
  from:    node;
  to_:    node;
  cost: int
}
type graph = {
  nodes: node list;
  edges: edge list
}

let from_edges {edges=edges} node =
  edges +>
    List.filter (fun {to_=to_} -> node = to_)

let rec short_path graph start goal =
  if start = goal then
    0
  else
    let costs =
      List.map
	(fun {from=node; cost=cost} ->
	   cost + short_path graph start node) @@
	from_edges graph goal in
      match costs with
	| [] ->
	    failwith "no route!"
	| x::xs ->
	    List.fold_left min x xs

let nodes =
  ["A";"B";"C"]

let edges = [
  {from="A"; to_="B";cost=3};
  {from="B"; to_="C";cost=3};
  {from="A"; to_="C";cost=4};
]

let graph = {
  nodes = nodes;
  edges = edges;
}

let f _ =
  short_path graph "A" "C"

参考