Reachability - Algorithms

Algorithms

Algorithms for reachability fall into two classes: those that require preprocessing and those that do not. For the latter case, resolving a single reachability query can be done in linear time using algorithms such as breadth first search or iterative deepening depth-first search.

Preprocessing algorithms (such as a simplified Floyd–Warshall algorithm, or Thorup's algorithm for planar digraphs, which uses only O(n log n) time and space) create data structures which allow subsequent reachability queries to be answered in constant time (i.e., in a small fixed amount of time, independent of the size of the graph). Such algorithms (or their data structures) are sometimes called oracles, since the precomputed data structure allows any query to be answered immediately, similar to how Turing machine oracles answer questions. Many reachability algorithms (including the two mentioned above) can be easily extended to provide distance or approximate distance algorithms for graphs where each directed edge has a distance (usually called a weight).