دو الگوریتم سریع وکوتاه ترین مسیربرای همه زوج ها

By scanning the arcs in order of increasing weight, arcs are eliminated earlier. By scanning the nodes in a ‘pseudo-topological’ order, the computation time can further decrease. In acyclic directed networks one of the resulting all-pairs algorithms runs in O(mlogn+nm0)O(mlogn+nm0) time, where m0m0 denotes the number of ‘essential’ arcs, i.e., arcs that are indispensable in some shortest path.