В ациклическом ориентированном графе G = (V,E) кратчайшие пути из одной вершины можно найти за время O(V + E), если проводить релаксацию рёбер в порядке, заданном топологическим упорядочением вершин.