Spath is a static C++ library for finding the shortest paths in graphs using various algorithms. The library provides efficient and versatile implementations suitable for different graph densities and use cases.
- Dijkstra's Algorithm (Low density version)
- Optimized for graphs with low density
- Dijkstra's Algorithm (High density version)
- Optimized for graphs with high density
- Ford-Bellman Algorithm
- Supports graphs with negative weight edges.
- Johnson's Algorithm
- Efficient for handling multiple queries for graphs with negative weights
- Floyd-Warshall Algorithm
- Comprehensive all-pairs shortest path solution for dense graphs.
- A* Algorithm
- Optimized for pathfinding with heuristics in weighted graphs.
| Algorithm | Best Use Case | Time Complexity |
|---|---|---|
| Dijkstra (sparse) | Sparse graphs, non-negative weights | O((V + E) * log V) |
| Dijkstra (dense) | Dense graphs, non-negative weights | O(V^2) |
| Ford-Bellman | Graphs with negative weights | O(V * E) |
| Johnson | Sparse graphs, all-pairs shortest paths | O(V^2 * log V + V * E) |
| Floyd-Warshall | Dense graphs, all-pairs shortest paths | O(V^3) |
| A* | Pathfinding with heuristics | O(m*log(n)*complexity(heuristic)) |
Clone our library. then build and install with cmake
mkdir build
cd build
cmake ..
cmake --build . --target Spath
cmake --install .
This will add our library to your system path. After that you can use it like:
#include <spath/spath.hpp>We have tests.cpp with included header. On each push tests from this file will be run. The tests will use Catch2 framework.
We benchmarked our algorithms (bench.cpp) with help of Google Benchmark. You can see results in Github Actions.
This project is licensed under the MIT License.