日元的

Question

我试图实现Yen提出的Bellman-Ford算法的优化，以及Bannister提出的随机加速

我正在跟踪班尼斯特

我已经能够成功地实现最初的Bellman-Ford算法，这是一个变体，包括算法的早期终止（当顶点距离没有变化时退出），以及Yen对算法的第一次改进（论文中的算法3）。

然而，我在实现Yen的第二个改进和Bannister-Eppstein随机改进（算法4）方面遇到了一些困难

文中给出的日元第二次改进的伪码是

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）行的语言令人困惑。

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

按数字顺序迭代顶点是什么意思？

关于我的代码的一些附加信息：我的算法将图形对象作为参数，它具有顶点（[0，n]）和边（[source，destination，weight]）的列表属性

编辑：论文中关于算法的一些额外信息：

“正如Yen所观察到的，也有可能以不同的方式改进算法，方法是更仔细地选择外循环每次迭代中边缘松弛的顺序，以便保证每次迭代都有两次正确的松弛，最后一次可能除外。具体地说，从so开始对顶点进行任意编号urce顶点，设G是由从编号较低的顶点到编号较高的顶点的边构成的子图，并设G− 是由从编号较高的顶点到编号较低的顶点的边形成的子图。然后是G和G− 都是有向无环图，并且顶点的编号是G的拓扑编号，与G的拓扑编号相反−. Yen算法的每次迭代都按拓扑顺序处理这两个子图。"

Answer 1

使用Fisher--Yates来洗牌除s之外的顶点。例如，您可以将顶点s、a、b、c、d、e、f和洗牌到f、a、c、e、d、b。然后您可以指定连续的数字s-