使用字典，图和列表，我试图实现Dijkstra算法与Clojure中的BFS。问题是我无法让它正常工作;当我要求它返回带权值的解时，它不会工作，当我要求它生成没有权值的图时，它也不会工作。问题很可能发生在BFS函数;我将非常感谢任何帮助。我试着在网上搜索信息，并与我的一些同学交谈，但不幸的是，它根本没有帮助。
文件:e-roads-2020-full。CLJ +项目。clj都在GitHub https://github.com/wfgemyd/clojure
;; state 0 - not encountered at all
;; state 1 - in the open queue
;; state 2 - current vertex
;; state 3 - visited
(defn al-papi [queue graph] ;;looks for the best vertex and dist
(loop [queue queue
best-distance nil
best-vertex nil]
(if (empty? queue)
best-vertex
(let [queue-label (first queue)
queue-vertex (get @(:vertices graph) queue-label)]
(if (or (nil? best-vertex) (< @(:distance queue-vertex) best-distance))
(recur (rest queue) @(:distance queue-vertex) queue-vertex)
(recur (rest queue) best-distance best-vertex))))))
(defn graph-bfs!
([graph]
(graph-bfs! graph (first (keys @(:vertices graph)))))
([graph start]
(graph-bfs! graph start (fn [vertex] nil)))
([graph start func]
(graph-bfs! graph start func first))
([graph start func func-m]
(let [vertices @(:vertices graph)]
(loop [queue (list start)]
(when (not (empty? queue))
(let [current-label (if (= func-m al-papi)(func-m queue graph)(func-m queue))
rest-queue (rest-queue! queue current-label)
current-vertex (get vertices current-label)
visited-status (:visited current-vertex)
current-neighbors @(:neighbors current-vertex)
unseen-neighbors (filter
(fn [label]
(= @(:visited (get vertices label)) 0))
current-neighbors)
]
(dosync (ref-set visited-status 2))
(func current-vertex)
(dosync (ref-set visited-status 3))
(doseq [label unseen-neighbors]
(dosync
(ref-set (:visited (get vertices label)) 1)))
(recur (concat rest-queue unseen-neighbors))))))))
(defn graph-dijkstra-mark! [graph finish use-weights]
(let [vertices @(:vertices graph)
start-vertex (get vertices finish)]
(graph-reset! graph)
(dosync
(ref-set (:distance start-vertex) 0))
(if (not use-weights)
(graph-bfs! graph
finish
(fn [vertex]
(let [next-distance (inc @(:distance vertex))]
(doseq [neighbor-label @(:neighbors vertex)]
(let [neighbor (get vertices neighbor-label)]
(if (= @(:visited neighbor) 0)
(dosync
(ref-set (:distance neighbor) next-distance))))))))
(graph-bfs! graph
finish
(fn [vertex]
(doseq [neighbor-label @(:neighbors vertex)]
(let [neighbor (get vertices neighbor-label)
next-distance (+ @(:distance vertex) (get-edge-weight graph (:label vertex) neighbor-label))]
(println "There is bfs!")
(when (or (= @(:visited neighbor) 0) (> @(:distance neighbor) next-distance))
(dosync
(ref-set (:distance neighbor) next-distance))))))
al-papi))))
找到了错误，它在反向跟踪函数中，它返回了ref而不是函数中需要的实际数据，加上函数"al-papi"返回的是最佳顶点，而不是最佳顶点的:标签。