Shortest Paths

Nievergelt & Hinrichs · Ch. 7 · Algorithms and Data Structures

Dijkstra finds shortest paths from one source with non-negative weights in O((V+E) log V). Bellman-Ford handles negative edges in O(VE). Floyd-Warshall finds all-pairs shortest paths in O(V³).

Dijkstra's algorithm

Maintain a priority queue of vertices by tentative distance. Extract the minimum, relax its neighbors. Greedy: once a vertex is finalized, its distance is optimal. Requires non-negative weights.

Scheme

; Dijkstra on a small weighted graph
; Graph: ((vertex (neighbor weight) ...) ...)

(define graph
  (list (list "S" (list "A" 3) (list "B" 10))
        (list "A" (list "C" 1))
        (list "B" (list "T" 6) (list "C" 2))
        (list "C" (list "T" 4) (list "B" 2))
        (list "T")))

(define (neighbors g v)
  (let ((entry (assoc v g)))
    (if entry (cdr entry) (list))))

; Simplified Dijkstra (no priority queue, O(V^2))
(define (dijkstra g start)
  (let loop ((unvisited (map car g))
             (dist (map (lambda (v)
                          (cons (car v) (if (equal? (car v) start) 0 999999)))
                        g)))
    (if (null? unvisited) dist
        (let* ((u (car (sort unvisited
                    (lambda (a b) (< (cdr (assoc a dist))
                                     (cdr (assoc b dist)))))))
               (d-u (cdr (assoc u dist)))
               (nbrs (neighbors g u))
               (new-dist (fold-left
                          (lambda (d nb)
                            (let* ((v (car nb))
                                   (w (cadr nb))
                                   (alt (+ d-u w))
                                   (cur (cdr (assoc v d))))
                              (if (< alt cur)
                                  (map (lambda (p)
                                         (if (equal? (car p) v)
                                             (cons v alt) p)) d)
                                  d)))
                          dist nbrs)))
          (loop (filter (lambda (v) (not (equal? v u))) unvisited)
                new-dist)))))

(define result (dijkstra graph "S"))
(for-each (lambda (p)
            (display (car p)) (display ": ")
            (display (cdr p)) (newline))
          result)

; Dijkstra on a small weighted graph
; Graph: ((vertex (neighbor weight) ...) ...)

(define graph
  (list (list "S" (list "A" 3) (list "B" 10))
        (list "A" (list "C" 1))
        (list "B" (list "T" 6) (list "C" 2))
        (list "C" (list "T" 4) (list "B" 2))
        (list "T")))

(define (neighbors g v)
  (let ((entry (assoc v g)))
    (if entry (cdr entry) (list))))

; Simplified Dijkstra (no priority queue, O(V^2))
(define (dijkstra g start)
  (let loop ((unvisited (map car g))
             (dist (map (lambda (v)
                          (cons (car v) (if (equal? (car v) start) 0 999999)))
                        g)))
    (if (null? unvisited) dist
        (let* ((u (car (sort unvisited
                    (lambda (a b) (< (cdr (assoc a dist))
                                     (cdr (assoc b dist)))))))
               (d-u (cdr (assoc u dist)))
               (nbrs (neighbors g u))
               (new-dist (fold-left
                          (lambda (d nb)
                            (let* ((v (car nb))
                                   (w (cadr nb))
                                   (alt (+ d-u w))
                                   (cur (cdr (assoc v d))))
                              (if (< alt cur)
                                  (map (lambda (p)
                                         (if (equal? (car p) v)
                                             (cons v alt) p)) d)
                                  d)))
                          dist nbrs)))
          (loop (filter (lambda (v) (not (equal? v u))) unvisited)
                new-dist)))))

(define result (dijkstra graph "S"))
(for-each (lambda (p)
            (display (car p)) (display ": ")
            (display (cdr p)) (newline))
          result)

Bellman-Ford

Relax all edges V-1 times. Handles negative weights. Detects negative cycles on the V-th pass. O(VE).

Floyd-Warshall

All-pairs shortest paths. Three nested loops: for each intermediate vertex k, for each pair (i,j), check if going through k is shorter. O(V³).

Neighbors

Cross-references

🎰 Grinstead Ch.11 — Markov chains on graphs: random walks and stationary distributions

← Graphs by june.kim Geometric Algorithms →