abhinavDhulipala/sp

Shortest Path

Dijkstra Prioriy Queue

CB-Cities

Compile

• Run mkdir build && cd build && cmake -DCMAKE_BUILD_TYPE=Release /path/to/CMakeLists.txt.

• Run make clean && make -jN (where N is the number of cores).

Run

• To run the dijkstra shortest path ./sp ../sf.mtx, because the executable sp would be generated inside the build directory.

• Running just ./sp will run the shortest path for the sample graph whose output is:

5 dist 21.2
4 dist 20.7
6 dist 11.5
3 dist 9.1
1 dist 0
2 dist 7.5

Run tests

• Run ./sptest -s (for a verbose output) or ctest -VV.

• Run ./sptest -l to see available test options

Run python interface

Requires Python3

• Create a virtual environment: virtualenv env and activate: source env/bin/activate
• Install dependencies: pip3 install -r requirements.txt or pip install -r requirements.txt
• Benchmark Dijkstra PQ vs iGraph: python3 ./interface.py

Run python benchmarks

Requires Python3

• Create a virtual environment: virtualenv env and activate: source env/bin/activate
• Install dependencies: pip3 install -r requirements.txt or pip install -r requirements.txt
• Benchmark Dijkstra PQ vs iGraph: python3 ./benchmark_dijkstra.py