Editing Floyd–Warshall algorithm
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 28: | Line 28: | ||
==Warshall's algorithm== | ==Warshall's algorithm== | ||
− | A special case of the Floyd–Warshall algorithm is ''Warshall's algorithm'', which tests only for reachability | + | A special case of the Floyd–Warshall algorithm is ''Warshall's algorithm'', which tests only for reachability. If two vertices are linked by an edge, we assign the edge any finite weight (such as 0 or 1), otherwise we assign it an infinite weight. If, at the end, we find the distance from one vertex to another to be finite, then they are connected, since a path existed using only finite-weight edges (that is, ones that actually exist); otherwise, if no such path exists, the entry in the matrix will be infinity. Notice that we can replace "finite" by 1, "infinite" by 0, addition with logical AND, and <code>min</code> with logical OR, and preserve existing logic. This yields the following implementation of Warshall's algorithm: |
<pre> | <pre> | ||
input adj | input adj | ||
Line 42: | Line 42: | ||
[[Category:Algorithms]] | [[Category:Algorithms]] | ||
− |