Я пытаюсь реализовать оптимизацию алгоритма Беллмана-Форда, предложенного Йеном, и рандомизированное ускорение, предложенное Баннистером и Эппштейном в python.
Я просматриваю статью Баннистера и Эппштейна на тему, котораяможно найти здесь
Мне удалось успешно реализовать оригинальный алгоритм Беллмана-Форда, вариант, который включает досрочное завершение алгоритма (выход, если не изменилось расстояние до вершин)) и первое усовершенствование алгоритма Йеном (алгоритм 3 в статье).
Однако у меня возникли некоторые проблемы при реализации второго улучшения Йена и рандомизированного улучшения Баннистер-Эппштейна (алгоритмы 4 и 5 в статье).
Псевдокод, приведенный в статье для второго улучшения Йены, имеет вид
1. number the vertices arbitrarily, starting with s
2. C ← {s}
3. while C != ∅ do
4. for each vertex u in numerical order do
5. if u ∈ C or D[u] has changed since start of iteration then
6. for each edge uv in graph G+ do
7. relax(u, v)
8. for each vertex u in reverse numerical order do
9. if u ∈ C or D[u] has changed since start of iteration then
10. for each edge uv in graph G− do
11. relax(u, v)
12. C ← {vertices v for which D[v] changed}
Псевдокод для алгоритма Баннистера-Эппштейна (алгоритм 5) точно такой же, как и выше, за исключением первогоСтрока, в которой говорится:
1. number the vertices randomly such that all permutations with s first are equally likely
Я нахожувозраст в строках 1 и (4,8) сбивает с толку.
Что означает «нумерация вершин произвольно / случайно»?
Что означает перебирать вершины в числовом порядке?
Некоторая дополнительная информация о моем коде: Мои алгоритмы принимают объект Graph в качестве параметра, который имеет атрибуты списка вершин ([0, n]) и ребер ([источник, назначение, вес])
РЕДАКТИРОВАТЬ: Некоторые дополнительные сведения об алгоритмах из бумаги:
"Как заметил Йен, также возможно улучшить алгоритм по-другому, выбрав более тщательно порядок, в которомослабить ребра в каждой итерации внешнего цикла, чтобы гарантировать две правильные релаксации для каждой итерации, за исключением, возможно, последней.В частности, нумерация вершин произвольно начинается с исходной вершины, пусть G + будет подграфом, образованным ребрами, идущими из вершины с меньшим номером, в вершину с более высоким номером, и пусть G− будет подграфом, образованным ребрами, идущими из более высокой вершины.пронумерованная вершина к вершине с меньшим номером.Тогда G + и G− являются ориентированными ациклическими графами, а нумерация вершин является топологической нумерацией G + и обратной топологической нумерацией для G−.Каждая итерация алгоритма Йена обрабатывает каждый из этих двух подграфов в топологическом порядке. "