这是一个创建于 3768 天前的主题，其中的信息可能已经有所发展或是发生改变。
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算法还是不怎么理解, 希望有人帮忙解惑一下.
这篇博文的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算法还是不怎么理解, 希望有人帮忙解惑一下.
 |
1
theJian 2014-08-18 16:04:18 +08:00  1
bellman-ford是通过不断进行“松弛”操作得到最短路的，flag记录的是 是否本轮有节点被松弛，如果没有节点能再“松弛”，最短路也就得出了，可以跳出循环。
|
 |
2
GtDzx 2014-08-18 17:10:38 +08:00
这里也有做POJ的小伙伴
|
 |
4
wisatbff 2014-08-18 17:57:14 +08:00
这种技巧叫剪枝。
|
Select Language