Module algorithms_edu::algo::graph::shortest_path

Modules

bellman_ford	An implementation of the Bellman-Ford algorithm. The algorithm finds the shortest path between a starting node and all other nodes in the graph. The algorithm also detects negative cycles. If a node is part of a negative cycle then the minimum cost for that node is set to f32::NEG_INFINITY
dijkstra	This file contains an implementation of Dijkstra's shortest path algorithm from a start node to a specific ending node. Dijkstra can also be modified to find the shortest path between a starting node and all other nodes in the graph. However, in this implementation since we're only going from a starting node to an ending node we can employ an optimization to stop early once we've visited all the neighbors of the ending node.
floyd_warshall	This file contains an implementation of the Floyd-Warshall algorithm to find all pairs of shortest paths between nodes in a graph. We also demonstrate how to detect negative cycles and reconstruct the shortest path.