关于网上的一段 POJ1860 代码松弛操作的疑问

2014-08-18 15:33:16 +08:00
 razrlele
http://blog.csdn.net/lyhvoyage/article/details/19281013

这篇博文的Bellman-Ford 算法代码里面的松弛操作的一部分:

for(int i = 1; i <= n - 1; i++)
{
bool flag = false;
for(int j = 0; j < C; j++)
{
int a = p[j].a, b = p[j].b;
double r = p[j].rate, c = p[j].cost;
if(dis[b] < (dis[a] - c) * r)
{
dis[b] = (dis[a] - c) * r;
flag = true;
}

}
if(!flag)
break;
这里为什么加一个flag变量呢?
我把flag去掉了一样可以AC, 并且时间也是0ms, 不是很理解作者在这里加flag的意图.

对于Bellman-Ford算法还是不怎么理解, 希望有人帮忙解惑一下.
2148 次点击
所在节点    问与答
4 条回复
theJian
2014-08-18 16:04:18 +08:00
bellman-ford是通过不断进行“松弛”操作得到最短路的,flag记录的是 是否本轮有节点被松弛,如果没有节点能再“松弛”,最短路也就得出了,可以跳出循环。
GtDzx
2014-08-18 17:10:38 +08:00
这里也有做POJ的小伙伴
razrlele
2014-08-18 17:28:33 +08:00
@GtDzx 弱菜啊弱菜啊,多多指教啊
wisatbff
2014-08-18 17:57:14 +08:00
这种技巧叫剪枝。

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/128551

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX