贝尔曼·福特(Bellman Ford)和一届奥林匹克竞赛? [英] Bellman Ford and One Olympiad Questions?

问题描述

三天前，我参加了一次奥林匹克考试.我遇到了一个很好的问题，如下.

I took an Olympiad Exam three days ago. I ran into a nice question as follows.

我们知道bellman-ford算法会检查每个步骤中的所有边缘，如果存在，则会检查每个边缘，

We know the bellman-ford algorithm checks all edges in each step, and for each edge if,

然后更新 d(v)，以使 w(u，v)是边缘(u，v)的权重，并且 d(u)是顶点 u 的最佳查找路径的长度.如果第一步中我们没有不更新顶点，则算法终止.假设该算法用于从图G中具有 n 个顶点且在 k<之后的顶点的所有 s 路径中找到所有最短路径.n 次迭代已完成，以下哪一项是正确的?

then d(v) being updated such that w(u,v) is the weight of edge (u, v) and d(u) is the length of best finding path for vertex u. if in one step we have no update for vertexes, the algorithms terminates. Supposing this algorithm for finding all shortest path from vertex s in graph G with n vertex after k < n iterations is finished, which of the following is correct?

1. 距 s 的所有最短路径中的边数最多为 k-1

1. number of edges in all shortest paths from s is at most k-1

1. 来自 s 的所有最短路径的权重最多为 k-1

1. weight of all shortest paths from s is at most k-1

1. 图形没有负循环.

谁可以讨论这些选项?

推荐答案

1不正确.首先，我们总是找到具有k条边的最短路径(如果有的话).而且，如果我们碰巧以最短路径树的拓扑顺序放宽弧线，那么尽管最短路径树可能任意深，我们还是会进行一次迭代收敛.

1 is incorrect. First of all, we always find shortest paths with k edges, if any. But also, if we happen to relax the arcs in the topological order of a shortest path tree, then we converge in one iteration, despite the fact that the shortest path tree may be arbitrarily deep.

s --> t --> u --> v

Relax s->t, t->u, u->v; shortest path from s->v is three hops,
but B--F has made two iterations.

2是不正确的，因为谁知道权重是什么?

2 is incorrect, because who knows what the weights are?

  100
s --> t

Relax s->t; weight is 100, but B--F has made two iterations.

3是正确的，因为根据平均参数，至少一个负周期的弧不会松弛.假设 v1，...，vn 为一个循环.由于弧线是松弛的，因此我们有 d(vi)+ len(vi-> vi + 1)-d(vi + 1)> = 0 .对所有 i 的不等式求和，并望远镜化 d 项，以简化为 sum_i len(vi-> vi + 1)> = 0 ，表示周期是非负的.

3 is correct, because by an averaging argument at least one arc of a negative cycle would be unrelaxed. Let v1, ..., vn be a cycle. Since the arcs are relaxed, we have d(vi) + len(vi->vi+1) - d(vi+1) >= 0. Sum the inequalities for all i and telescope the d terms to simplify to sum_i len(vi->vi+1) >= 0, which says that the cycle is nonnegative.

这篇关于贝尔曼·福特(Bellman Ford)和一届奥林匹克竞赛?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！