1# Shortpath sample
2This directory contains an example that solves the single source shortest path problem.
3
4It 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.
5
6This 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`.
7
8Note 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.
9
10Silent mode prints run time only, regular mode prints the shortest path length, and verbose mode prints out the shortest path.
11
12The 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.
13
14## Building the example
15```
16cmake <path_to_example>
17cmake --build .
18```
19
20## Running the sample
21### Predefined make targets
22* `make run_shortpath` - executes the example with predefined parameters.
23* `make perf_run_shortpath` - executes the example with suggested parameters to measure the oneTBB performance.
24
25### Application parameters
26Usage:
27```
28shortpath [#threads=value] [verbose] [silent] [N=value] [start=value] [end=value] [-h] [#threads]
29```
30* `-h` - prints the help for command line options.
31* `n-of-threads` - number of threads to use; a range of the form low[:high], where low and optional high are non-negative integers or `auto` for a platform-specific default number.
32* `verbose` - prints diagnostic output to screen.
33* `silent` - no output except elapsed time.
34* `N` - number of nodes in graph.
35* `start` - node to start path at.
36* `end` - node to end path at.
37