-
Notifications
You must be signed in to change notification settings - Fork 1
Home
There are 2 implementations of Dijsktra algorithm: low-, high-density. The weights SHOULD be non-negative. When the common structure of graph is rather well defined and clear, it is suitable to choose the correct mode.
Both algorithms accept start vertex (int), end vertex (int) and the graph in form of the adjacency list.
It returns the pair of values: weight of the shortest path and the path itself.
It solves the same problem as Dijkstra except that the weights can be negative, BUT there shouldn't be negative cycles.
The algorithm accepts start vertex (int) and the graph in form of the adjacency list.
It returns the vector of shortest paths from start to all vertexes of the graph.
It makes sense to use this algorithm only if you have negative weights (without negative cycles) and at the same time you should perform multiple queries. Then the algorithm calculates the Johnson's potentials and returns them.
In turn, the user can add these potentials to the initial graph and then invoke more efficient Dijkstra algorithms as much as needed.
A* is a modified version of Dijkstra's algorithm, which can be more efficient for computing path to a one specific vertice. It needs heuristic function that estimates distance between two vertices and gives higher priority to the ones closer to target vertice.
The Floyd Warshall algorithm computes distance from all to all and the paths can also be restored.
Lee's algorithm is actually just a version of bfs that explicitly stores "levels" of search and can only be used with unweighted graphs. Typically used for searching paths on a game map. Our implementation works for rectangular mazes defined by boolean arrays. You can also print the found path using print_maze_path.
- Converter - the class whose task is to convert between one graph's representation to another one. Supported representations:
- // TODO
- Graph algorithms
//TODO
Google Benchmark and Boost Graph Library are used to do benchmark testing.