A “String Algorithm” for Shortest Path in Directed Networks

Any shortest-path algorithm A for undirected networks can be combined with the simple cutting procedure C described below so as to form a shortest-path algorithm for directed networks. If a directed network has v nodes and e arcs, then a shortest path joining two specified nodes can be found by min[v, 1/2(e + 2)] or fewer applications of A, each followed by an application; of C.