CrossClj

0.1.0 docs

SourceDocs



RECENT

    xpe/dijkstra

    Clojars

    Jan 15, 2015


    OWNER
    Bluemont Labs
    Washington, DC
    bluemontlabs.com

    Readme

    Index of all namespaces


    « Project + dependencies

    Dijkstra's shortest-paths algorithm in Clojure.

    dijkstra.coreDocsSource
    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.
    
    [1]: http://en.wikipedia.org/wiki/Edsger_W._Dijkstra
    [2]: https://docs.oracle.com/javase/8/docs/api/java/lang/Long.html
    The README below is fetched from the published project artifact. Some relative links may be broken.

    dijkstra

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

    Usage

    (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

    License

    Copyright 2015 David James.

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