我对Bellman-Ford做了一点修改,所以它只起到“有用”的放松作用。这就是说,D(v)意味着的放松得到了更新。
define Relax(u, v):
if d(v) > d(u) + w(u,v) //w(u,v) = weight of edge u->v
d(v) = d(u) + w(u,v)
INIT // our usual initialization.
Queue Q
Q ← s // Q holds vertices whose d(v) values have been updated recently.
While (Q not empty)
{
u ← Frontof(Q);
for each neighbor v of u
{
Relax(u, v)
if d(v) was updated by Relax and v not in the Q //Here s where we re a bit smarter
ADD v to End of Q. //since we add to Q if
//the relaxation changed d(v)
}
}
现在, 如果所有最短路径都最多有 k 弧。 那么最坏的运行时间是 O( V*k), 因为我们只通过这个智能版本的 k 弧。 这比 { k} & lt; {\\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
有人能告诉我一个图表类型吗? 这个改良版没有比最初的Bellman-Ford算法更好吗?这就是说,最优的性能是O(V*E)