我这里有一个更聪明的贝尔曼福特版本：
//Queue Q; source s; vertices u, v
Q ← s // Q holds vertices whose d(v) values have been updated recently.
While (Q !empty)
{
u ← Dequeue(Q)
for each neighbor v of u
{
Relax(u, v)
if d(v) was updated by Relax and v not in Q
Enqueue(v)
}
}
任何人都能想到一种类型的图，该算法被（v*e）时间复杂度限制在V＝α顶点，e＝α边的边界上。
我想看看这其中的陷阱在哪里。
最佳答案
自从我上次考虑短路径算法以来已经很多年了，如果我忘了什么，请纠正我。
首先，我们将首先排除负加权循环情况，但它可能是最坏情况下性能的来源。
假设你访问了一个完整的图表。从第一个节点开始，您将对v-1节点排队，因为所有节点都是s的邻居。假设您运气不好，并且您排队的最后一个节点是所有节点最短路径的一部分。因此，必须对v-2节点（所有节点，减去源节点和正在计算的节点）进行排队。现在让我们非常不走运，假设您排队的最后一个节点再次成为所有剩余节点路径的一部分…你必须把V-3节点排队等。
所以如果一切都出错了，您将计算出v-1*v-2*…*3*2*1个节点。你应该很容易知道这和e有什么关系。
对于每个节点，你在做什么？检查每一个邻居。每个节点都有v-1邻居。
我们已经达到了算法的最坏情况复杂性。
如果我记得很清楚，BELMAN Ford算法检查每个边以确保没有负加权循环，你也应该这样做，并且将1增加到V-1，AKA（ⅤⅤe）最坏情况复杂度。
关于algorithm - Bellman-Ford变化，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/10679359/