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.

all-pairs shortest path | Bellman-Ford algorithm | Dijkstra's algorithm | graph distance | graph geodesic | shortest path problem