Floyd-Warshall algorithm:
Floyd-Warshall algorithm for shortest paths in a directed graph
Description
Floyd-Warshall algorithm for shortest paths in a directed graph.
Usage
floyd(x)
Arguments
x
The adjacency matrix of a directed graph. A positive number in x[i, j] indicates that there is an arrow
from i to j and it also shows the cost of going from i to j. Hence, the algorithm will find not only the shortest path but also the with the smallest cost. A value of zero means that there is no path.
Put positive number only, as negative will cause problems.
Value
A matrix, say z, with 0 and positive numbers. If z[i, j] is zero it means that there is no path going from i to j. If z[i, j] has a positive value it means that there is a path from i to j and its value is equal to the cost of going from i to j.
Details
The Floyd-Warshall algorithm is designed to find the shortest path (if it exists) between two nodes in a graph.
References
Floyd, Robert W. (1962). Algorithm 97: Shortest Path. Communications of the ACM. 5(6): 345.
Warshall, Stephen (1962). A theorem on Boolean matrices. Journal of the ACM. 9 (1): 11-12.