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