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

[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算法还是不怎么理解, 希望有人帮忙解惑一下.

[theJian]

bellman-ford是通过不断进行“松弛”操作得到最短路的，flag记录的是 是否本轮有节点被松弛，如果没有节点能再“松弛”，最短路也就得出了，可以跳出循环。

[GtDzx]

这里也有做POJ的小伙伴

[razrlele]

@GtDzx 弱菜啊弱菜啊,多多指教啊

[wisatbff]

这种技巧叫剪枝。