blocks|key|139765|text|%251不正确。首先，我们总是找到有k条边的最短路径。而且，如果我们碰巧在最短路径树的拓扑顺序中放松弧，那么我们在一次迭代中收敛，尽管最短路径树可能是任意深的。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|139766|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.|code-block|syntax|javascript|139767|2是不正确的，因为谁知道权重是多少？|139768|++100
s+-->+t

Relax+s->t;+weight+is+100,+but+B--F+has+made+two+iterations.|139769|3是正确的，因为通过平均论点，负循环中至少有一条弧是不松弛的。假设v1,+...,+vn是一个循环。因为弧线是松弛的，所以我们有d(vi)+%2B+len(vi->vi%2B1)+-+d(vi%2B1)+>=+0。将所有i的不等式相加，并缩小d项以简化为sum_i+len(vi->vi%2B1)+>=+0，这表明该周期是非负的。|offset|length|style|CODE|139770|entityMap^0|0|0|0|0|X|B|1S|10|2W|1|37|1|3D|O|0^^$0|@$1|2|3|4|5|6|7|S|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|T|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|U|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|V|8|@]|9|@]|A|$E|F]]|$1|K|3|L|5|6|7|W|8|@$M|X|N|Y|O|P]|$M|Z|N|10|O|P]|$M|11|N|12|O|P]|$M|13|N|14|O|P]|$M|15|N|16|O|P]]|9|@]|A|$]]|$1|Q|3|-4|5|6|7|17|8|@]|9|@]|A|$]]]|R|$]]

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.
<pre><code>s --&gt; t --&gt; u --&gt; v

Relax s-&gt;t, t-&gt;u, u-&gt;v; shortest path from s-&gt;v is three hops,
but B--F has made two iterations.
</code></pre>
2 is incorrect, because who knows what the weights are?
<pre><code> 100
s --&gt; t

Relax s-&gt;t; weight is 100, but B--F has made two iterations.
</code></pre>
3 is correct, because by an averaging argument at least one arc of a negative cycle would be unrelaxed. Let <code>v1, ..., vn</code> be a cycle. Since the arcs are relaxed, we have <code>d(vi) + len(vi-&gt;vi+1) - d(vi+1) &gt;= 0</code>. Sum the inequalities for all <code>i</code> and telescope the <code>d</code> terms to simplify to <code>sum_i len(vi-&gt;vi+1) &gt;= 0</code>, which says that the cycle is nonnegative.

blocks|key|2920373|text|我认为选项3是不正确的，因为要知道是否存在负权重循环，Bellman+ford算法需要运行n次。首先n-1次计算最短路径，然后再一次检查距离是否有任何改善，这意味着存在负权重循环。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2920374|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

i think option 3 is incorrect because to know if there is negative weight cycle ,the Bellman ford algorithm needs to run n times.
first n-1 times to calculate the shortest path and then one more time to check if there is any improvement in the distances if there are improvements ,it means there is a negative weight cycle.

I took an Olympiad Exam three days ago. I ran into a nice question as follows.
We know the bellman-ford algorithm checks all edges in each step, and for each edge if,
<h1>d(v)&gt;d(u)+w(u,v)</h1>
then <code>d(v)</code> being updated such that <code>w(u,v)</code> is the weight of edge <code>(u, v)</code> and <code>d(u)</code> is the length of best finding path for vertex <code>u</code>. if in one step we have <code>no update for vertexes</code>, the algorithms <code>terminates</code>. Supposing this algorithm for finding all shortest path from vertex <code>s</code> in graph G with <code>n</code> vertex after <code>k &lt; n</code> iterations is finished, which of the following is correct?
<blockquote>
<ol>
<li>number of edges in all shortest paths from <code>s</code> is at most <code>k-1</code></li>
</ol>
</blockquote>
<blockquote>
<ol start="2">
<li>weight of all shortest paths from <code>s</code> is at most <code>k-1</code></li>
</ol>
</blockquote>
<blockquote>
<ol start="3">
<li>Graph has no negative cycle.</li>
</ol>
</blockquote>
Who can discuss on these options ?

Bellman Ford and One Olympiad Questions?

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

我三天前参加了奥林匹克竞赛考试。我遇到了一个很好的问题，如下所示。我们知道贝尔曼-福特算法在每一步中检查所有的边，并且对于每条边，d( v) >d(u)+w(u，v)然后更新d(v)，使得w(u,v)是边(u, v)的权重，d(u)是顶点u的最佳发现路径的长度。如果在一个步骤中我们有了no update for ver...

问行李员福特和一个奥林匹克竞赛的问题？
EN

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问行李员福特和一个奥林匹克竞赛的问题？EN

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问行李员福特和一个奥林匹克竞赛的问题？
EN