Bellman-Ford 算法的 Yen's & Bannister-Eppstein 优化
Yen's & Bannister-Eppstein optimization of Bellman-Ford algorithm
我正在尝试实现 Yen 提出的 Bellman-Ford 算法的优化，以及 Bannister & Eppstein 在 python 中提出的随机加速。
我正在关注 Bannister & Eppstein 关于该主题的论文 here
我已经能够成功地实现原始的 Bellman-Ford 算法，一个包括提前终止算法的变体（当顶点距离没有变化时退出），以及 Yen 对算法的第一次改进（算法3 在论文中）。
但是，我在实施 Yen 的第二次改进和 Bannister-Eppstein 随机改进（论文中的算法 4 和 5）时遇到了一些麻烦。
Yen第二次改进论文中给出的伪代码是
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}
Bannister-Eppstein 算法（算法 5）的伪代码与上面完全相同，除了第一行指出：
1. number the vertices randomly such that all permutations with s first are equally likely
我发现第 1 行和第 (4,8) 行的语言令人困惑。
"number the vertices arbitrarily / randomly"是什么意思？
按数字顺序遍历顶点是什么意思？
关于我的代码的一些附加信息：我的算法将 Graph 对象作为参数，该对象具有顶点 ([0,n]) 和边 ([source,destination,weight]) 的列表属性
编辑：论文中有关算法的一些额外信息：
"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."
使用 Fisher--Yates 打乱 s 以外的顶点。例如，您可能有顶点 s、a、b、c、d、e、f 并洗牌到 f、a、c、e、d、b。然后就可以赋值连续的数s->0,f->1,a->2,c->3,e->4,d->5,b->6。数字顺序为 s、f、a、c、e、d、b。相反的数字顺序是 b、d、e、c、a、f、s。 G+ 中的边从编号较低的顶点到编号较高的顶点，例如 c->b。 G- 中的边从编号较高的顶点到编号较低的顶点。
我正在尝试实现 Yen 提出的 Bellman-Ford 算法的优化，以及 Bannister & Eppstein 在 python 中提出的随机加速。
我正在关注 Bannister & Eppstein 关于该主题的论文 here
我已经能够成功地实现原始的 Bellman-Ford 算法，一个包括提前终止算法的变体（当顶点距离没有变化时退出），以及 Yen 对算法的第一次改进（算法3 在论文中）。
但是，我在实施 Yen 的第二次改进和 Bannister-Eppstein 随机改进（论文中的算法 4 和 5）时遇到了一些麻烦。
Yen第二次改进论文中给出的伪代码是
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}
Bannister-Eppstein 算法（算法 5）的伪代码与上面完全相同，除了第一行指出：
1. number the vertices randomly such that all permutations with s first are equally likely
我发现第 1 行和第 (4,8) 行的语言令人困惑。
"number the vertices arbitrarily / randomly"是什么意思？
按数字顺序遍历顶点是什么意思？
关于我的代码的一些附加信息：我的算法将 Graph 对象作为参数，该对象具有顶点 ([0,n]) 和边 ([source,destination,weight]) 的列表属性
编辑：论文中有关算法的一些额外信息：
"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."
使用 Fisher--Yates 打乱 s 以外的顶点。例如，您可能有顶点 s、a、b、c、d、e、f 并洗牌到 f、a、c、e、d、b。然后就可以赋值连续的数s->0,f->1,a->2,c->3,e->4,d->5,b->6。数字顺序为 s、f、a、c、e、d、b。相反的数字顺序是 b、d、e、c、a、f、s。 G+ 中的边从编号较低的顶点到编号较高的顶点，例如 c->b。 G- 中的边从编号较高的顶点到编号较低的顶点。