SimGrid
3.14.159
Versatile Simulation of Distributed Systems
|
Functions | |
void | xbt_floyd_algorithm (xbt_graph_t g, double *adj, double *d, xbt_node_t *p) |
Floyd-Warshall algorithm for shortest path finding. More... | |
void xbt_floyd_algorithm | ( | xbt_graph_t | g, |
double * | adj, | ||
double * | d, | ||
xbt_node_t * | p | ||
) |
Floyd-Warshall algorithm for shortest path finding.
From wikipedia:
The Floyd-Warshall algorithm takes as input an adjacency matrix representation of a weighted, directed graph (V, E). The weight of a path between two vertices is the sum of the weights of the edges along that path. The edges E of the graph may have negative weights, but the graph must not have any negative weight cycles. The algorithm computes, for each pair of vertices, the minimum weight among all paths between the two vertices. The running time complexity is Θ(|V|3).