Crate floyd_warshall

This crate contains an implementation of the Floyd-Warshall algorithm to solve the all-pairs-shortest-paths problem in undirected graphs.

Structs

Path

This represents a sequence of nodes. The length is also saved, and when exists = false, this means “there is no path”.

PathMatrix

This matrix is a solution to the APSP problem, calculated by the Floyd-Warshall algorithm. It contains the intermediate nodes on the shortest path between every two nodes.

Functions

floyd_warshall

This function computes a distance matrix containing the shortest paths between every two nodes in the graph. By using the Floyd-Warshall algorithm, this is computed in O(V^(3)) runtime.