Python – Yen’s & Bannister-Eppstein optimization of the Bellman-Ford algorithm

I’m trying to implement in python the optimization of Yen’s Bellman-Ford algorithm and Bannister & Eppstein’s random speedup.

I’m following Bannister and Eppstein’s paper on the topic and can find here

I have been able to successfully implement the original Bellman-Ford algorithm, a variant that includes early termination of the algorithm (exit when the vertex distance does not change), and the first improvement of the algorithm by Yen (algorithm 3 in paper).

However, I had some trouble implementing Yen’s second improvement and Bannister-Eppstein’s random improvement (algorithms 4 and 5 in the paper).

The

pseudocode for Yen’s second improvement given in the paper 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 pseudocode for the Bannister-Eppstein algorithm (algorithm 5) is exactly the same as above, except that the first line declares:

1. number the vertices randomly such that all permutations with s first are equally likely

I find the language of lines 1 and (4,8) confusing.

What does “arbitrary/random number vertice” mean?

What does it mean to traverse vertices in numerical order?

Some additional information about my code: My algorithm takes as a parameter a Graph object that has list properties for vertices ([0,n]) and edges ([source,destination,weight]

).

Edit: Some extra information about algorithms in 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 scramble 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. You can then 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 order of numbers is B, D, E, C, A, F, S. Edges in G+ go from lower-numbered vertices to higher-numbered vertices, such as c->b. Edges in G- go from higher-numbered vertices to lower-numbered vertices.