Strict Standards: Non-static method DB::connect() should not be called statically, assuming $this from incompatible context in /group/project/aicat/web/lib/database.php on line 32

Strict Standards: Non-static method DB::parseDSN() should not be called statically, assuming $this from incompatible context in /usr/share/pear/DB.php on line 520

Strict Standards: Non-static method DB::isError() should not be called statically, assuming $this from incompatible context in /usr/share/pear/DB.php on line 557

Strict Standards: Non-static method DB::isError() should not be called statically, assuming $this from incompatible context in /group/project/aicat/web/lib/database.php on line 34

Strict Standards: Non-static method DB::isError() should not be called statically, assuming $this from incompatible context in /group/project/aicat/web/lib/database.php on line 92

Strict Standards: Non-static method DB::isError() should not be called statically, assuming $this from incompatible context in /usr/share/pear/DB/common.php on line 1009

Strict Standards: Non-static method DB::isManip() should not be called statically, assuming $this from incompatible context in /usr/share/pear/DB/common.php on line 2200

Strict Standards: Non-static method DB::isError() should not be called statically, assuming $this from incompatible context in /group/project/aicat/web/lib/database.php on line 97

Strict Standards: Non-static method DB::connect() should not be called statically, assuming $this from incompatible context in /group/project/aicat/web/lib/database.php on line 32

Strict Standards: Non-static method DB::parseDSN() should not be called statically, assuming $this from incompatible context in /usr/share/pear/DB.php on line 520

Strict Standards: Non-static method DB::isError() should not be called statically, assuming $this from incompatible context in /usr/share/pear/DB.php on line 557

Strict Standards: Non-static method DB::isError() should not be called statically, assuming $this from incompatible context in /group/project/aicat/web/lib/database.php on line 34
Catalogue of Artificial Intelligence Techniques

Catalogue of Artificial Intelligence Techniques

   

Jump to: Top | Entry | References | Comments

View Maths as: Images | MathML


Strict Standards: Non-static method DB::isManip() should not be called statically, assuming $this from incompatible context in /usr/share/pear/DB/common.php on line 2200

Strict Standards: Non-static method DB::isError() should not be called statically, assuming $this from incompatible context in /usr/share/pear/DB/common.php on line 1217

Strict Standards: Non-static method DB::isError() should not be called statically, assuming $this from incompatible context in /usr/share/pear/DB/common.php on line 1666

Strict Standards: Non-static method DB::isError() should not be called statically, assuming $this from incompatible context in /usr/share/pear/DB.php on line 1387

Strict Standards: Non-static method DB::isError() should not be called statically, assuming $this from incompatible context in /usr/share/pear/DB/common.php on line 1683

Strict Standards: Non-static method DB::isError() should not be called statically, assuming $this from incompatible context in /group/project/aicat/web/lib/database.php on line 113

Strict Standards: Non-static method DB::isManip() should not be called statically, assuming $this from incompatible context in /usr/share/pear/DB/common.php on line 2200

Strict Standards: Non-static method DB::isError() should not be called statically, assuming $this from incompatible context in /usr/share/pear/DB/common.php on line 1217

Strict Standards: Non-static method DB::isError() should not be called statically, assuming $this from incompatible context in /usr/share/pear/DB/common.php on line 1666

Strict Standards: Non-static method DB::isError() should not be called statically, assuming $this from incompatible context in /usr/share/pear/DB.php on line 1387

Strict Standards: Non-static method DB::isError() should not be called statically, assuming $this from incompatible context in /usr/share/pear/DB/common.php on line 1683

Strict Standards: Non-static method DB::isError() should not be called statically, assuming $this from incompatible context in /group/project/aicat/web/lib/database.php on line 113

Strict Standards: Non-static method DB::isManip() should not be called statically, assuming $this from incompatible context in /usr/share/pear/DB/common.php on line 2200

Strict Standards: Non-static method DB::isError() should not be called statically, assuming $this from incompatible context in /usr/share/pear/DB/common.php on line 1217

Strict Standards: Non-static method DB::isError() should not be called statically, assuming $this from incompatible context in /usr/share/pear/DB/common.php on line 1666

Strict Standards: Non-static method DB::isError() should not be called statically, assuming $this from incompatible context in /usr/share/pear/DB.php on line 1387

Strict Standards: Non-static method DB::isError() should not be called statically, assuming $this from incompatible context in /usr/share/pear/DB/common.php on line 1683

Strict Standards: Non-static method DB::isError() should not be called statically, assuming $this from incompatible context in /group/project/aicat/web/lib/database.php on line 113

Strict Standards: Non-static method DB::isManip() should not be called statically, assuming $this from incompatible context in /usr/share/pear/DB/common.php on line 2200

Strict Standards: Non-static method DB::isError() should not be called statically, assuming $this from incompatible context in /usr/share/pear/DB/common.php on line 1217

Strict Standards: Non-static method DB::isError() should not be called statically, assuming $this from incompatible context in /usr/share/pear/DB/common.php on line 1666

Strict Standards: Non-static method DB::isError() should not be called statically, assuming $this from incompatible context in /usr/share/pear/DB.php on line 1387

Strict Standards: Non-static method DB::isError() should not be called statically, assuming $this from incompatible context in /usr/share/pear/DB/common.php on line 1683

Strict Standards: Non-static method DB::isError() should not be called statically, assuming $this from incompatible context in /group/project/aicat/web/lib/database.php on line 113

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:


Strict Standards: Non-static method DB::isManip() should not be called statically, assuming $this from incompatible context in /usr/share/pear/DB/common.php on line 2200

Strict Standards: Non-static method DB::isError() should not be called statically, assuming $this from incompatible context in /usr/share/pear/DB/common.php on line 1217

Strict Standards: Non-static method DB::isError() should not be called statically, assuming $this from incompatible context in /usr/share/pear/DB/common.php on line 1666

Strict Standards: Non-static method DB::isError() should not be called statically, assuming $this from incompatible context in /usr/share/pear/DB.php on line 1387

Strict Standards: Non-static method DB::isError() should not be called statically, assuming $this from incompatible context in /usr/share/pear/DB/common.php on line 1683

Strict Standards: Non-static method DB::isError() should not be called statically, assuming $this from incompatible context in /group/project/aicat/web/lib/database.php on line 113


Comments:


Strict Standards: Non-static method DB::isManip() should not be called statically, assuming $this from incompatible context in /usr/share/pear/DB/common.php on line 2200

Strict Standards: Non-static method DB::isError() should not be called statically, assuming $this from incompatible context in /usr/share/pear/DB/common.php on line 1217

Strict Standards: Non-static method DB::isError() should not be called statically, assuming $this from incompatible context in /usr/share/pear/DB/common.php on line 1666

Strict Standards: Non-static method DB::isError() should not be called statically, assuming $this from incompatible context in /usr/share/pear/DB.php on line 1387

Strict Standards: Non-static method DB::isError() should not be called statically, assuming $this from incompatible context in /usr/share/pear/DB/common.php on line 1683

Strict Standards: Non-static method DB::isError() should not be called statically, assuming $this from incompatible context in /group/project/aicat/web/lib/database.php on line 113
Add Comment

No comments.