python - Bellman-Ford 算法的 Yen's & Bannister-Eppstein 优化

Question

我正在尝试在 python 中实现 Yen 提出的 Bellman-Ford 算法的优化，以及 Bannister & Eppstein 提出的随机加速。

我正在关注 Bannister 和 Eppstein 关于该主题的论文，可以找到 here

我已经能够成功地实现原始的 Bellman-Ford 算法，一个包括算法提前终止的变体(当顶点距离没有变化时退出)，以及 Yen 对算法的第一次改进(算法 3 in论文)。

但是，我在实现 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) 行的语言令人困惑。

“任意/随机编号顶点”是什么意思？

按数字顺序遍历顶点是什么意思？

关于我的代码的一些附加信息:我的算法将 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."

Answer 1

使用 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- 中的边从编号较高的顶点到编号较低的顶点。