Если график ациклический, лучше всего обходить вершины в топологическом порядке. Это означает, что необходима только одна итерация алгоритма.
Для циклических графов без отрицательных ребер вы можете использовать общий алгоритм кратчайшего пути, как описано в этом файле PDF ( sssp.pdf ) с очередью Fifo, это может посещать меньше вершин, чем стандартный алгоритм Беллмана-Форда который зацикливается на вершинах, а затем ребер. На практике подход очереди Fifo часто быстрее, чем использование очереди приоритетов (Dijkstra), как упоминалось в этом ответе ( Существуют ли более быстрые алгоритмы, чем Dijkstra? ). Однако недостатком этого подхода является то, что в отличие от стандартного алгоритма Беллмана-Форда этот алгоритм не завершится, если граф имеет отрицательные циклы.