[ALGO] A Star Search

[bobluppes]

A Star Search

The A Star algorithm (or A*) is an informed search algorithm which finds the shortest path between a start vertex and a target vertex. The search is guided by a heuristic, which prioritizes the traversal order of the candidate paths.

See the wikipedia entry for more details.

Syntax

The algorithm should have the following syntax:

/**
 * @brief Finds the shortest path between a start_vertex and target_vertex
 *        using the A* search algorithm.
 *
 * @param graph The graph to search in.
 * @param start_vertex The starting vertex for the search.
 * @param target_vertex The target vertex to reach.
 * @param heuristic A heuristic function estimating the cost from a vertex to the target.
 * @return An optional containing the shortest path if found, or std::nullopt if no path exists.
 */
template <typename V, typename E, graph_type T, typename HEURISTIC_T, typename WEIGHT_T = decltype(get_weight(std::declval<E>()))>
  requires std::is_invocable_r_v<WEIGHT_T, HEURISTIC_T&, vertex_id_t>
std::optional<graph_path<WEIGHT_T>> a_star_search(
    const graph<V, E, T> &graph, vertex_id_t start_vertex, vertex_id_t target_vertex,
    const HEURISTIC_T &heuristic);

This should live in the graaf::algorithm namespace under include/graaflib/algorithm/shortest_path.h.

Definition of Done

This issue is done when:

• The algorithm is implemented
• The new function has a javadoc-style comment explaining the interface
• Appropriate tests are added under test/graaflib/algorithm/shortest_path_test.cpp
• A test coverage of at least 95% is reached
• A documentation entry is added under docs/docs/algorithms under the appropriate category
  • Just adding a short description and the algorithm syntax here is fine
  • See the wiki on how to build the documentation locally
• The algorithm is added to the list of algorithms in README.md

[ndcroos]

I would like to work on this.

[bobluppes]

Hi @ndcroos, super happy to hear that! Assigning this to you ;)