在 OCaml 中实现 Dijkstra 算法时遇到问题

Question

我正在尝试在 OCaml 中实现 Dijkstra 算法，这是我正在关注的伪代码：

到目前为止，我已经编写了这些函数，将所有内容都放入其中会太长，此时可能没有必要。但我会给出他们的类型。

(* init_dist build the distances (distance Map) between the nodes given a nodes list. *)
let init_dist nodes source
val init_dist : node list -> node -> float DistMap.t = <fun>

(* min_elt_and_key return a (node,float) tuple, by finding the minimum key and returning its key with it. *)
let min_elt_and_key map ~compare_element
val min_elt_and_key : 'a DistMap.t -> compare_element:('a -> 'a -> int) -> node * 'a = <fun>

(* update_distances updates dMap and prevMap based on n1 and n2, returns a tuple of Map *) 
let update_distances n1 n2 dMap prevMap

(* find_minimum returns the minimum node based on the distance map. *)
let find_minimum nodes_Q first_node map
val find_minimum : node list -> node -> float DistMap.t -> node = <fun>

这就是我所在的位置。

let dijkstra graph source target =
  let nodes = Graph.nodes in
  let distanceMap = init_dist nodes source in
  let prevMap = DistMap.empty in
  let nodes_Q = Graph.nodes in
  let rec dijkstra_aux dMap pMap nodes_Q target =

(Graph.nodes 类型为 node list)

我的问题是我不知道如何通过 nodes_Q 找到最小值，删除它，然后继续。循环在 OCaml 中有 unit 类型，所以在这里进行命令式编程会很难退出，而且最终目标是 return 映射元组（dist 和 prev）。另外还会出现另一个问题，我如何为 while 中的 for 循环编写代码？我基本上编写了编写算法所需的每个函数，但组装它们并不是一件容易的事。

我看过这个 link : http://rosettacode.org/wiki/Dijkstra%27s_algorithm#OCaml

但是，我几个月前才开始使用 OCaml 编码，我的数据结构似乎与我的数据结构大不相同。

你会推荐我什么来实现这一点？

谢谢。

Answer 1

思考函数式语言中的命令式循环的方法是将循环体重新想象为一个函数。在循环中操作的任何值都是函数的参数。为了进行循环的下一次迭代，该函数使用参数的新值递归调用自身。

在您的案例中操作的值是 Q、dist 和 prev。所以你可以想象你的伪代码中的最后一个循环是这样的：

let rec dijkstra_aux q dist prev =
    if empty q then
        (dist, prev)
    else
        let min_elt = smallest_element_of q in
        let q' = remove_element q min_elt in
        let (dist', prev') = update_neighbors q dist prev in
        dijkstra_aux q' dist' prev'

在 OCaml 中实现 Dijkstra 算法时遇到问题

Having troubles implementing Dijkstra algorithm in OCaml

algorithm

ocaml

dictionary

list

dijkstra