Catalogue of Artificial Intelligence Techniques

   

Jump to: Top | Entry | References | Comments

View Maths as: Images | MathML

Floyd-Warshall Algorithm

Aliases: Floyd's Algorithm, Roy-Floyd Algorithm, Warshall's Algorithm

Keywords: all, directed, graph, pairs, path, shortest, theory

Categories: Game Theory


Author(s): Alex Price

The Floyd-Warshall algorithm is an algorithm for solving the all pairs shortest paths problem on weighted, directed graphs. That is to say, it finds the shortest route between all possible pairs of vertices on a graph where all the edges have a specific weight and direction. Negative weight edges may be present, but we assume there are no negative weight cycles. The running time complexity is Θ(n) (it runs in cubic time)

The algorithm works like this:
Assume the vertices of the directed graph G are V = {1,2,...,n}, consider a subset {1,2,...,k} for some k. For any pair of vertices i,j ∈ V, consider all paths from i to j whose intermediate vertices are all taken from {1,2,...,k}, and let p be a minimum weight path from among them. The algorithm exploits a relationship between path p and shortest paths from i to j with all intermediate vertices in the set {1,2,...,k−1}. The relationship depends on whether or not k is an intermediate vertex of path p.

* If k is not an intermediate vertex of path p, then all intermediate vertices of path p are in the set {1,2,...,k-1}
* If k is an intermediate vertex of p then the algorithm breaks down the path into two parts, i to k (p₁) and k to j (p₂), p₁ and p₂ are the shortest paths between their two vertices with intermediate vertices in the set {1,2,...,k-1}


References:


Comments:

Add Comment

No comments.