Вариация алгоритмов Беллмана-Форда?

Question

У нас есть Направленный граф с 100 вершинами. v1 -> v2 -> ... v100 и веса всех ребер равны 1. Мы хотим использовать Bellman-ford для нахождения всех кратчайших путей от v1 до других вершин. Этот алгоритм на каждом этапе проверяет все ребра в произвольном порядке. если на каждом шаге кратчайшее расстояние v1 до всех остальных вершин не изменяется, этот алгоритм останавливается. количество шагов связано с проверкой порядка ребер. какой минимум и максимум шагов в этой задаче?

Решение: 2 и 100.

Как это решение будет достигнуто?

Answer 1

Решение 2, если края похожи

v1->v2
v1->v3
...

В этом случае первая итерация найдет расстояние от источника до каждого ребра, а вторая итерация не изменит вес и, следовательно, алгоритм остановится.

Решение 100, если

v1->v2->v3->...->v100 

.ie все находятся на прямой линии, чем нам нужно 99 итераций, чтобы обновить расстояние до 100-й вершины, и последняя итерация не изменит расстояние.