1
\$\begingroup\$

Below is an implementation of Dijkstra's shortest path algorithm. It's input graph is represented as an association list of source nodes to assoc of target node and arc weight.

My question is about the following, am I missing a way of simplifying min-path function used in reduce? Maybe the great and powerful loop could do reduce's job?

(defun dijkstra (source target graph)
  (labels ((min-path (&optional arc-1 arc-2)
             (let ((price-1 (cdr arc-1))
                   (price-2 (cdr arc-2)))
               (cond 
                 ((and (not (null arc-1)) (not (null arc-2))) (if (< price-1 price-2)
                                                                arc-1 arc-2) )
                 ((and (not (null arc-1)) (null (arc-2))) arc-1) 
                 ((and (not (null arc-2)) (null (arc-1))) arc-2))))
           (get-best-path (visited)
             (reduce #'min-path (loop for pick in visited 
                                      for start = (car pick) 
                                      for cost = (cdr pick) 
                                      append (loop for arc in (cdr (assoc start graph))
                                                   when (null (assoc (car arc) visited))
                                                   collect (cons (car arc) (+ cost (cdr arc))))))))
    (loop named main-loop
          with visited = (list (cons source 0))
          for best-arc = (get-best-path visited)

          when (not (null best-arc)) 
          do (push best-arc visited)  
          until (or (null best-arc)
                  (eql (car best-arc) target)) 
          finally 
          (format t "Found shortest path from ~A to ~A: ~A~%" source target best-arc)
          (return-from main-loop (cdr best-arc)))))

I'm new to Lisp, and I would appreciate any advice, especially on bad Lisp habits and bad Lisp style in my code, thanks.

UPD: new version with review comments applied - no warnings, unlike the original version.

(defun dijkstra (source target graph)
  (labels ((min-path (&optional arc-1 arc-2)
             (cond ((and arc-1 arc-2) (if (< (cdr arc-1) (cdr arc-2)) arc-1 arc-2))
                   (arc-1 arc-1)
                   (arc-2 arc-2)
                   (t nil)))
           (get-best-path (visited)
             (reduce #'min-path 
                     (loop for pick in visited 
                           for start = (car pick) 
                           for cost = (cdr pick) 
                           append (loop for arc in (cdr (assoc start graph))
                                        unless (assoc (car arc) visited)
                                        collect (cons (car arc) (+ cost (cdr arc))))))))
    (loop with visited = (list (cons source 0))
          for best-arc = (get-best-path visited)
          when best-arc do
          (push best-arc visited)  
          until (or (null best-arc) (eql (car best-arc) target)) 
          finally (return (cdr best-arc)))))
\$\endgroup\$
2
\$\begingroup\$

First, (not (null x)) is not very idiomatic; just use x instead.

Next, you are not handling all the cased in your cond (and you obviously mean (null arc-2) and not (null (arc-2))). If fact, I would drop the let and use nested ifs instead.

Finally, to answer your original question: of course loop can do everything reduce can, but if your intent is clearer with the latter, use it!

EDIT: unless is more idiomatic than when (null ...).

\$\endgroup\$
  • \$\begingroup\$ Wow, thanks, the (null (arc-2)) is an error that doesn't prevent the program from properly executing. Regarding all cases, it is "merely" a discipline matter right? \$\endgroup\$ – zzandy Mar 11 '13 at 13:58
  • \$\begingroup\$ If this error does not prevent proper execution, you are not testing all cases in your inputs. Checking all cases in cond is needed for clarity of your intent and error checking. \$\endgroup\$ – sds Mar 11 '13 at 14:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.