Reaching Algorithm

The so-called reaching algorithm can solve the shortest path problem (i.e., the problem of finding the graph geodesic between two given nodes) on an m-edge graph in O(m) steps for an acyclic digraph. This algorithm allows paths such that edges traversed in the direction opposite their orientation have a negative length.

No other algorithm can have better complexity because any other algorithm would have to at least examine every edge, which would itself take O(m) steps.

See also

All-Pairs Shortest Path, Bellman-Ford Algorithm, Dijkstra's Algorithm, Graph Distance, Graph Geodesic, Shortest Path Problem

This entry contributed by Andreas Lauschke

Explore with Wolfram|Alpha

Cite this as:

Lauschke, Andreas. "Reaching Algorithm." From MathWorld--A Wolfram Web Resource, created by Eric W. Weisstein.

Subject classifications