Finding the shortest path

The algorithms presented earlier traversed the graph vertex by vertex and returned a lazy sequence of all the nodes in the graph. They were convenient for illustrating the two primary ways of navigating the graph structures. However, a more common task would be to find the shortest path from one vertex to another. This means that we'll be interested only in the sequence of nodes that lie between them.

If we have an unweighted graph, such as the previous graphs, we'll usually count the distance as the number of "hops": a hop being the step between two neighboring nodes. The shortest path will have the fewest number of hops. Breadth-first search is, in general, a more efficient algorithm to use in this case.

Loom implements ...

Get Clojure for Data Science now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.