## 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,dijkstrareturns a map in this format, as doesrelax, 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.