Dijkstra Shortest Path | Graaf lib (original) (raw)

Dijkstra's algorithm computes shortest paths between nodes in weighted and unweighted graphs. In weighted graphs, edge weights should be non-negative. Dijkstra's algorithm is implemented with a priority queue and runs in O(|E|log|V|) for connected graphs, where |E| is the number of edges and |V| the number of vertices in the graph.

calculates the shortest path between on start_vertex and one end_vertex using Dijkstra's algorithm. Works on both weighted as well as unweighted graphs. For unweighted graphs, a unit weight is used for each edge.

template <typename V, typename E, graph_type T, typename WEIGHT_T = decltype(get_weight(std::declval<E>()))>
std::optional<graph_path<WEIGHT_T>> 
dijkstra_shortest_path(const graph<V, E, T>& graph, vertex_id_t start_vertex, vertex_id_t end_vertex);

Find the shortest paths from a source vertex to all other vertices in the graph using Dijkstra's algorithm.

template <typename V, typename E, graph_type T, typename WEIGHT_T = decltype(get_weight(std::declval<E>()))>
[[nodiscard]] std::unordered_map<vertex_id_t, graph_path<WEIGHT_T>>
dijkstra_shortest_paths(const graph<V, E, T>& graph, vertex_id_t source_vertex);