0.1.0 docs





    Jan 15, 2015

    Bluemont Labs
    Washington, DC


    Index of all namespaces

    « Project + dependencies

    Dijkstra's shortest-paths algorithm in Clojure.

    A Clojure implementation of the shortest path algorithm for single
    sources by Edsger Dijkstra [1].
    This code is based on Introduction to Algorithms (3rd Edition, 2009)
    by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford
    Stein, pages 643 to 659. Below, I abbreviate the book as ItA.
    Key details:
    * This code represents costs (i.e. edge weights) as Java primitive
    longs [2].
    * Costs must be non-negative.
    Differences with ItA:
    * I use the term 'cost' instead of 'weight' (used in ItA).
    * I setup the data structures a bit differently than ItA. This code
    considers vertexes (a set) and edges (a map of {[vertex-1 vertex-2]
    cost} as immutable. This affects the next point directly.
    * In the ItA Dijkstra pseudo-code, each vertex has two subproperties:
    a cost and a predecessor. This code uses a different approach because
    it treats the vertexes as immutable. Instead, the same information is
    kept in a map (usually called 'vcp' because the initials correspond to
    vertex, cost, predecessor). In these maps, each pair takes the form
    {vertex [cost predecessor]}. The main function, dijkstra returns a
    map in this format, as does relax, a supporting function.
    The README below is fetched from the published project artifact. Some relative links may be broken.


    A Clojure implementation of the shortest path algorithm for single sources by Edsger Dijkstra.


    (require '[dijkstra.core :refer [dijkstra]])
    (def vertexes #{:s :t :x :y :z})
    (def edges {[:s :t] 10
                [:s :y] 5
                [:t :x] 1
                [:t :y] 2
                [:y :t] 3
                [:y :x] 9
                [:x :z] 4
                [:z :x] 6
                [:y :z] 2
                [:z :s] 7})
    (dijkstra vertexes edges :s)

    Returns a [cost predecessor] value for each destination vertex from the source, :s:

    {:x [9 :t], :t [8 :y], :z [7 :y], :s [0 nil], :y [5 :s]}

    In other words, the lowest costs are:

    • 9 from :s to :x
    • 8 from :s to :t
    • 7 from :s to :z
    • 0 from :s to :s
    • 5 from :s to :y

    And the least-cost paths are:

    • [:s :y :t :x] for 9
    • [:s :y :t] for 8
    • [:s :y :z] for 7
    • [:s] for 0
    • [:s :y] for 5


    Copyright 2015 David James.

    Distributed under the Eclipse Public License either version 1.0 or (at your option) any later version.