Предыстория

Жил был алгоритм Форд-Беллмана. Разные люди его по всякому оптимизировали.
Например, популярен «Форд-Белман с очередью», также известный, как SPFA.

Здесь мы рассмотрим менее популярную версию «Форд-Белман с random shuffle».

(1) random_shuffle(edges.begin(), edges.end());
for (int run = 1; run; ) {
	run = 0;
        (2) random_shuffle(edges.begin(), edges.end());
	for (Edge e : edges)
		if (relax(e))
			run = 1;
}

Фазой назовём цикл по всем рёбрам. Обычный Форд-Беллман сделает не более V фаз.

История

Оказывается, в зависимости от того, где написать random_shuffle,
сделать один раз заранее, или делать в начале каждой фазы, многое зависит.

На худшем тесте матожидание числа фаз у одного из новых Форд-Беллманов равно V / 2, у другого V / 1.72.
Как думаете, у кого меньше? Скоро допишу сюда ответ и доказательства.