FLOYD-MUCHLAND

The Floyd-Warshall algorithm is an algorithm for determining the distances of the shortest paths between all pairs of vertices in a directed and weighted graph The Floyd-Warshall algorithm takes as input a directed and valued graph, described by an adjacency matrix giving the weight of an arc when it exists and the value ∞ otherwise. The weight of a path between two vertices is the sum of the weights on the arcs constituting this path. The arcs of the graph can have negative weights, but the graph must not have a strictly negative weight circuit. The algorithm calculates, for each pair of vertices, the minimum weight among all the paths between these two vertices.