我三天前参加了一场奥林匹克竞赛考试。我遇到了一个很好的问题,如下所示。
我们知道Bellman-Ford算法在每一步都检查所有边,对于每条边,如果满足以下条件:
d(v)>d(u)+w(u,v)
则更新d(v),其中w(u,v)是边(u, v)的权重,d(u)是顶点u的最佳路径长度。如果在一步中我们没有更新顶点,则算法终止。假设这个算法用于在图G中从顶点s找到所有最短路径,在执行k1.从s到所有最短路径上的边数最多为k-1 2.从s到所有最短路径的权重最大为k-1 3.图形没有负循环。
有谁可以讨论这些选项吗?
我们知道Bellman-Ford算法在每一步都检查所有边,对于每条边,如果满足以下条件:
d(v)>d(u)+w(u,v)
则更新d(v),其中w(u,v)是边(u, v)的权重,d(u)是顶点u的最佳路径长度。如果在一步中我们没有更新顶点,则算法终止。假设这个算法用于在图G中从顶点s找到所有最短路径,在执行k1.从s到所有最短路径上的边数最多为k-1 2.从s到所有最短路径的权重最大为k-1 3.图形没有负循环。
有谁可以讨论这些选项吗?