Предыстория

Жил был алгоритм Форд-Беллмана. Разные люди его по-всякому оптимизировали.
Например, популярен «Форд-Белман с очередью», также известный, как 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.
Как думаете, у кого меньше? Скоро допишу сюда ответ и доказательства.

Если вы любите математику, но не Форд-Беллмана, вот теорвер-составляющая

int i = 0, phase = 0;
p = [0, 1, ... n-1]
(1) random_shuffle(p.begin(), p.end()); 
for (int i = 0; i < n; phase++) {
	(2) random_shuffle(p.begin(), p.end()); 
	for (int x : p)
		if (x == i)
			i++;
}
// Найти матожидание phase в зависимости от того, где random_shuffle, в (1) или (2).

UPD: правильный ответ и доказательства записал eatmore, спасибо ему.