I am attempting to implement the optimizations of the Bellman-Ford algorithm proposed by Yen, and the randomized speedup proposed by Bannister & Eppstein in python.
I am following through Bannister & Eppstein's paper on the topic which can be found here
I have been able to successfully implement the original Bellman-Ford algorithm, a variant that includes early termination of the algorithm (exit when no changes to the vertices distance have changed), and Yen's first improvement to the algorithm (algorithm 3 in the paper).
However, I have had some trouble implementing Yen's second improvment, and Bannister-Eppstein randomized improvement (algorithms 4 & 5 in the paper).
The pseudocode given in the paper for Yen's second improvement is
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}
The pseudo code for Bannister-Eppstein's algorithm (algorithm 5) is exactly the same as above, expect for the first line which states :
1. number the vertices randomly such that all permutations with s first are equally likely
I find the language on lines 1 and (4,8) confusing.
What does it mean to "number the vertices arbitrarily / randomly"?
What does it mean to iterate through the vertices in numerical order?
Some additional info about my code: My algorithms take a Graph object as a parameter which has list attributes of vertices([0,n]) and edges([source,destination,weight])
EDIT: Some extra information about the algorithms from the paper:
"As Yen observed, it is also possible to improve the algorithm in a different way, by choosing more carefully the order in which to relax the edges within each iteration of the outer loop so that two correct relaxations can be guaranteed for each iteration except possibly the last. Specifically, number the vertices arbitrarily starting from the source vertex, let G+ be the subgraph formed by the edges that go from a lower numbered vertex to a higher numbered vertex, and let G− be the subgraph formed by the edges that go from a higher numbered vertex to a lower numbered vertex. Then G+ and G− are both directed acyclic graphs, and the numbering of the vertices is a topological numbering of G+ and the reverse of a topological numbering for G−. Each iteration of Yen’s algorithm processes each of these two subgraphs in topological order."
Use Fisher--Yates to shuffle the vertices other than s. For example, you might have vertices s, a, b, c, d, e, f and shuffle to f, a, c, e, d, b. Then you can assign consecutive numbers s->0, f->1, a->2, c->3, e->4, d->5, b->6. The numerical order is s, f, a, c, e, d, b. The reverse numerical order is b, d, e, c, a, f, s. The edges in G+ go from a lower numbered vertex to a higher, e.g., c->b. The edges in G- go from a higher numbered vertex to a lower.