Using dictionaries, graphs, and lists, I'm attempting to implement the Dijkstra algorithm with BFS in Clojure. The issue is that I can't get it to work correctly; it won't work when I ask it to return the solution with weights, and it also won't work when I ask it to produce the graph without weights. The problem occurs, most likely, at the BFS function; I would very appreciate any assistance with this. I tried to search for information online and spoke with some of my classmates, but unfortunately it didn't help at all.
The files: e-roads-2020-full.clj + project.clj are in 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))))