Intel® Threading Building Blocks.
Shortpath sample

This directory contains a simple example that solves the single source shortest path problem.

It is parameterized by N, a number of nodes, and a start and end node in [0..N). A graph is generated with N nodes and some random number of connections between those nodes. A parallel algorithm based on A* is used to find the shortest path.

This algorithm varies from serial A* in that it needs to add nodes back to the open set when the g estimate (shortest path from start to the node) is improved, even if the node has already been "visited". This is because nodes are added and removed from the open-set in parallel, resulting in some less optimal paths being explored. The open-set is implemented with the concurrent_priority_queue.

Note that since we re-visit nodes, the f estimate (on which the priority queue is sorted) is not technically needed, so we could use this same parallel algorithm with just a concurrent_queue. However, keeping the f estimate and using concurrent_priority_queue results in much better performance.

Silent mode prints run time only, regular mode prints the shortest path length, and verbose mode prints out the shortest path.

The generated graph follows a pattern in which the closer two pairs of node ids are together, the fewer hops there are in a typical path between those nodes. So, for example, the path between 5 and 7 likely has few hops whereas 14 to 78 has more and 0 to 9999 has even more, etc.