Зачем алгоритму Беллмана-Форда нужны проходы v-1?

Question

До сих пор я не видел графика, который требует более 2 проходов с использованием Bellman-Ford. У кого-нибудь есть пример, которому действительно нужно больше двух? (алгоритм говорит, что в худшем случае требуется проход v-1). Спасибо.

Answer 1

Сколько раз на самом деле зависит от порядка посещения, в лучшем случае посещение того, которое имеет отрицательный вес, для вещания в первую очередь, в худшем случае посещение его в последнем месте (так что вам всегда нужно много проходов распространять отрицательный вес на первый посещенный узел).

Answer 2

Более интересный пример: G=(V,E), V={1,...,n}, E={(j,1,2j), (i,i-1,1) for all j=3,...,n and i=2,...,n}. (Каждое ребро имеет форму (a,b,w), что означает от a до b, а w - вес / расстояние ребра.)

График выглядит так:

Расстояние до узла 1 обновляется n-1 раз.