为什么spfa算法判断负环时是判断 一个点进队超过n次?_noip吧_百度贴吧
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&签到排名：今日本吧第个签到，本吧因你更精彩，明天继续来努力！
本吧签到人数：0成为超级会员，使用一键签到本月漏签0次！成为超级会员，赠送8张补签卡连续签到：天&&累计签到：天超级会员单次开通12个月以上，赠送连续签到卡3张
关注：18,286贴子：
为什么spfa算法判断负环时是判断 一个点进队超过n次?收藏
为什么spfa算法判断负环时是判断 一个点进队超过n次，可我感觉应该是超过n-1就应该有负环了？
在职研究生报名入口,在职研究生名校报名
你的意思是说一个点的图肯定负环？
有向图1-&2（负边权），或者只有一个点，你能说有负环吗。。
这应该是一个环和一条链的区别吧
登录百度帐号推荐应用
为兴趣而生，贴吧更懂你。或图论（167）
Time Limit:
MS (Java/Others)&&&&Memory Limit:
K (Java/Others)
Total Submission(s): 1710&&&&Accepted Submission(s): 424
Problem Description
It has recently been discovered how to run open-source software on the Y-Crate gaming device. A number of enterprising designers have developed Advent-style games for deployment on the Y-Crate. Your job is to test a number of these
designs to see which are winnable.
Each game consists of a set of up to 100 rooms. One of the rooms is the start and one of the rooms is the finish. Each room has an energy value between -100 and +100. One-way doorways interconnect pairs of rooms.
The player begins in the start room with 100 energy points. She may pass through any doorway that connects the room she is in to another room, thus entering the other room. The energy value of this room is added to the player's energy. This process continues
until she wins by entering the finish room or dies by running out of energy (or quits in frustration). During her adventure the player may enter the same room several times, receiving its energy each time.
The input consists of several test cases. Each test case begins with n, the number of rooms. The rooms are numbered from 1 (the start room) to n (the finish room). Input for the n rooms follows. The input for each room consists of
one or more lines containing:
the energy value for room i
the number of doorways leaving room i
a list of the rooms that are reachable by the doorways leaving room i
The start and finish rooms will always have enery level 0. A line containing -1 follows the last test case.
In one line for each case, output &winnable& if it is possible for the player to win, otherwise output &hopeless&.
Sample Input
Sample Output
题意是说有n个房间，然后给你每个房间能够到达的房间，每个房间还有一个能量值（有正有负），让你从第一个房间出发判断能否到达第n个房间，一开始你有100能量值，如果能量值为负则失败，当然你也可以从一个房间在返回已经走过的并且可到达的房间去补充能量值。
首先你要判断他能不能到达n号房间，如果到达不了，则直接失败。如果能够到达，则判断他的能量值是否大于0，如果有环的话，则证明此点加入队列的次数要大于等于n，然后判断此点能否到达n即可。无环的话，则求从1号点到n号点的最长路即可。
#include&stdio.h&
#include&string.h&
#include&queue&
bool g[107][107],reach[107][107];
int energy[107],power[107],count[107];
void floyd()
for(int i=1;i&=n;i++)
for(int j=1;j&=n;j++)
for(int k=1;k&=n;k++)
reach[j][k]=(reach[j][k]||reach[j][i]&&reach[i][k]);
bool spfa(int now)
queue&int&q;
memset(power,0,sizeof(power));
memset(count,0,sizeof(count));
q.push(now);
power[1]=100;
while(!q.empty())
int now=q.front();
count[now]++;
if(count[now]&=n) return reach[now][n];//如果某个点的次数大于n，则存在正环
for(int i=1;i&=n;i++)
if(g[now][i]&&power[now]+energy[i]&power[i]&&power[now]+energy[i]&0)
q.push(i);
power[i]=power[now]+energy[i];
return power[n]&0;
int main()
while(scanf(&%d&,&n)!=EOF)
memset(g,false,sizeof(g));
memset(reach,false,sizeof(reach));
for(int i=1;i&=n;i++)
scanf(&%d%d&,&energy[i],&num);
while(num--)
scanf(&%d&,&door);
g[i][door]=
reach[i][door]=
if(!reach[1][n])
printf(&hopeless\n&);
if(spfa(1))
printf(&winnable\n&);
printf(&hopeless\n&);
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：512304次
积分：11640
积分：11640
排名：第973名
原创：681篇
转载：10篇
评论：108条
人来到这世界后，命运注定了他必须要拼搏，奋斗，坚持，勇敢地走下去，走出属于自己的道路，没有人能不劳而获。上天赐予了你宝贵的生命，必定要让你在一生中，坚持，奋斗到最后一秒，燃烧尽生命的火焰。本帖子已过去太久远了，不再提供回复功能。带权最短路 Dijkstra, SPFA, Bellman-Ford, ASP, Floyd-Warshall 算法分析 - Blog - Renfei Song图论中，用来求最短路的方法有很多，适用范围和时间复杂度也各不相同。本文主要介绍的算法的代码主要来源如下：Dijkstra: Algorithms（《算法概论》）Sanjoy Dasgupta, Christos Papadimitriou, Umesh V《算法竞赛入门经典—训练指南》刘汝佳、陈峰。SPFA (Shortest Path Faster Algorithm): Data Structure and Algorithms Analysis in C, 2nd ed.（《数据结构与算法分析》）Mark Allen Weiss.Bellman-Ford: Algorithms（《算法概论》）Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani.ASP (Acyclic Shortest Paths): Introduction to Algorithms - A Creative Approach（《算法引论—一种创造性方法》）Udi Manber.Floyd-Warshall: Data Structure and Algorithms Analysis in C, 2nd ed.（《数据结构与算法分析》）Mark Allen Weiss.它们的使用限制和运行时间如下：Dijkstra: 不含负权。运行时间依赖于优先队列的实现，如 $O\left(\left(\mid V\mid+\mid E\mid\right)\log\mid V\mid\right)$SPFA: 无限制。运行时间$O\left(k\cdot\mid E\mid\right)\ \left(k \ll \mid V\mid\right)$Bellman-Ford：无限制。运行时间$O\left(\mid V\mid\cdot\mid E\mid\right)$ASP: 无圈。运行时间$O\left(\mid V\mid+\mid E\mid\right)$Floyd-Warshall: 无限制。运行时间$O\left(\mid V\mid^3\right)$其中 1~4 均为单源最短路径 (Single Source Shortest Paths) 算法； 5 为全源最短路径 (All Pairs Shortest Paths) 算法。顺便说一句，为什么没有点对点的最短路径？如果我们只需要一个起点和一个终点，不是比计算一个起点任意终点更节省时间么？答案还真不是，目前还没有发现比算从源点到所有点更快的算法。图的表示本文中，前四个算法的图都采用邻接表表示法，如下：struct Edge
int weight;
Edge(int f, int t, int w):from(f), to(t), weight(w) {}
int num_nodes;
int num_edges;
vector&Edge& edges;
vector&int& G[max_nodes]; // 每个节点出发的边编号
int p[max_nodes]; // 当前节点单源最短路中的上一条边
int d[max_nodes]; // 单源最短路径长Dijkstra 方法Dijkstra 方法依据其优先队列的实现不同，可以写成几种时间复杂度不同的算法。它是图论－最短路中最经典、常见的算法。关于这个方法，网上有许多分析，但是我最喜欢的还是《算法概论》中的讲解。为了理解 Dijkstra 方法，首先回顾一下无权最短路的算法。无权最短路算法基于 BFS，每次从源点向外扩展一层，并且给扩展到的顶点标明距离，这个距离就是最短路的长。我们完全可以仿照这个思路，把带权图最短路问题规约到无权图最短路问题——只要把长度大于 1 的边填充进一些「虚顶点」即可。如下图所示。这个办法虽然可行，但是显然效率很低。不过，Dijkstra 方法$EC, EB, ED$分别出发，经过一系列「虚节点」，依次到达$D, B, C$ 。为了不在虚节点处浪费时间，出发之前，我们设定三个闹钟，时间分别为$4, 3, 2$提醒我们预计在这些时刻会有重要的事情发生（经过实际节点）。更一般地说，假设现在我们处理到了某个顶点$u$，和$u$相邻接的顶点为$v_1, v_2, \ldots, v_n$，它们和$u$的距离为$d_1, d_2, \ldots, d_n$。我们为$v_1, v_2, \ldots, v_n$各设定一个闹钟。如果还没有设定闹钟，那么设定为$d$ ；如果设定的时间比$d$晚，那么重新设定为$d$（此时我们沿着这条路比之前的某一条路会提前赶到）。每次闹钟响起，都说明可能经过了实际节点，我们都会更新这些信息，直到不存在任何闹钟。综上所述，也就是随着 BFS 的进行，我们一旦发现更近的路径，就立即更新路径长，直到处理完最后（最远）的一个顶点。由此可见，由于上述「虚顶点」并非我们关心的实际顶点，因此 Dijkstra 方法的处理方式为：直接跳过了它们。还需要解决的一个问题，就是闹钟的管理。闹钟一定是从早到晚按顺序响起的，然而我们设闹钟的顺序却不一定按照时间升序，因此需要一个优先队列来管理。Dijkstra 方法实现的效率严重依赖于优先队列的实现。一个使用标准库容器适配器 priority_queue 的算法版本如下：typedef pair&int, int& HeapNode;
void Dijkstra(int s)
priority_queue& HeapNode, vector&HeapNode&, greater&HeapNode& & Q;
for (int i=0; i&num_nodes; ++i)
d[i] = __inf;
Q.push(make_pair(0, s));
while (!Q.empty()) {
pair&int, int& N = Q.top();
int u = N.second;
if (N.first != d[u]) continue;
for (int i=0; i&G[u].size(); ++i) {
Edge &e = edges[G[u][i]];
if (d[e.to] & d[u] + e.weight) {
d[e.to] = d[u] + e.weight;
p[e.to] = G[u][i];
Q.push(make_pair(d[e.to], e.to));
}Bellman-Ford：一个简单的想法Dijkstra 方法的本质是进行一系列如下的更新操作：然而，如果边权含有负值，那么 Dijkstra 方法将不再适用。原因解释如下。假设最终的最短路径为：不难看出，如果按照 $ (s,\ u_1),\ (u_1,\ u_2),\ \ldots ,(u_k,\ t) $ 的顺序执行上述更新操作，最终$ t $的最短路径一定是正确的。而且，只要保证上述更新操作全部按顺序执行即可，并不要求上述更新操作是连续进行的。Dijkstra 算法所运行的更新序列是经过选择的，而选择基于这一假设：$ s\rightarrow t $的最短路一定不会经过和$s$距离大于$ l(s,\ t) $的点。对于正权图这一假设是显然的，对于负权图这一假设是错误的。因此，为了求出负权图的最短路径，我们需要保证一个合理的更新序列。但是，我们并不知道最终的最短路径！因此一个简单的想法就是：更新所有的边，每条边都更新$\mid V\mid -1$次。由于多余的更新操作总是无害的，因此算法（几乎）可以正确运行。等等，为什么是$\mid V\mid -1$次？这是由于，任何含有$\mid V\mid$个顶点的图两个点之间的最短路径最多含有$\mid V\mid -1$条边。这意味着最短路不会包含环。理由是，如果是负环，最短路不存在；如果是正环，去掉后变短；如果是零环，去掉后不变。算法实现中唯一一个需要注意的问题就是负值圈 (negative-cost cycle)。负值圈指的是，权值总和为负的圈。如果存在这种圈，我们可以在里面滞留任意长而不断减小最短路径长，因此这种情况下最短路径可能是不存在的，可能使程序陷入无限循环。好在，本文介绍的几种算法都可以判断负值圈是否存在。对于 Bellman-Ford 算法来说，判断负值圈存在的方法是：在$\mid V\mid -1$次循环之后再执行一次循环，如果还有更新操作发生，则说明存在负值圈。Bellman-Ford 算法的代码如下：bool Bellman_Ford(int s)
for (int i=0; i&num_nodes; ++i)
d[i] = __inf;
for (int i=0; i&num_nodes; ++i) {
bool changed = false;
for (int e=0; e&num_edges; ++e) {
if (d[edges[e].to] & d[edges[e].from] + edges[e].weight
&& d[edges[e].from] != __inf) {
d[edges[e].to] = d[edges[e].from] + edges[e].weight;
p[edges[e].to] = e;
changed = true;
if (!changed) return true;
if (i == num_nodes && changed) return false;
return false; // 程序应该永远不会执行到这里
}注记：如果某次循环没有更新操作发生，以后也不会有了。我们可以就此结束程序，避免无效的计算。上述程序中第 11 行的判断：如果去掉这个判断，只要图中存在负值圈函数就会返回 false。否则，仅在给定源点可以达到负值圈时才返回 false。SPFA：一个改进的想法看来，Bellman-Ford 算法多少有些浪费。这里介绍的 SPFA 可以算作是 Bellman-Ford 的队列改进版。在 Dijkstra 方法中，随着 BFS 的进行，最短路一点一点地「生长」。然而如果存在负权，我们的算法必须允许「绕回去」的情况发生。换句话说，我们需要在某些时候撤销已经形成的最短路。同时，我们还要改变 Bellman-Ford 算法盲目更新的特点，只更新有用的节点。SPFA 中，一开始，我们把源点 $s$放入队列中，然后每次循环让一个顶点$u$出队，找出所有与$u$邻接的顶点$v$，更新最短路，并当$v$不在队列里时将它入队。循环直到队列为空（没有需要更新的顶点）。可以显示出 SPFA 和 Bellman-Ford 算法相比的一个重大改进的最经典的一个例子，就是图为一条链的情形。容易看出，如果存在负值圈，这个算法将无限循环下去。因此需要一个机制来确保算法得以中止。由于最短路最长只含有$\mid V\mid -1$条边，因此如果任何一个顶点已经出队$\mid V\mid +1$次，算法停止运行。SPFA 的代码如下：bool in_queue[max_nodes];
int cnt[max_nodes];
bool SPFA(int s)
queue&int& Q;
memset(in_queue, 0, sizeof(in_queue));
memset(cnt, 0, sizeof(cnt));
for (int i=0; i&num_nodes; ++i)
d[i] = __inf;
in_queue[s] = true;
Q.push(s);
while (!Q.empty()) {
in_queue[u=Q.front()] = false;
for (int i=0; i&G[u].size(); ++i) {
Edge &e = edges[G[u][i]];
if (d[e.to] & d[u] + e.weight) {
d[e.to] = d[u] + e.weight;
p[e.to] = G[u][i];
if (!in_queue[e.to]) {
Q.push(e.to);
in_queue[e.to] = true;
if (++cnt[e.to] & num_nodes)
return false;
return true;
}我们已经给出 SPFA 的运行时间为$O\left(k\cdot\mid E\mid\right)\ \left(k \ll \mid V\mid\right)$。实际上，可以期望$k&2$。但是可以构造出使 SPFA 算法变得很慢的针对性数据。Acyclic Shortest Path如果图是无圈的（acyclic）（或称为有向无环图，DAG），那么情况就变的容易了。我们可以构造一个拓扑升序序列，由拓扑排序的性质，无圈图的任意路径中，顶点都是沿着「拓扑升序序列」排列的，因此我们只需要按照这个序列执行更新操作即可。显然，这样可以在线性时间内解决问题。实现上，拓扑排序和更新可以一趟完成。这种算法的代码如下：int indegree[max_nodes];
void asp(int s)
queue&int& Q;
for (int i=0; i&num_nodes; ++i) {
d[i] = __inf;
indegree[i] = 0;
for (int i=0; i&num_edges; ++i)
++indegree[edges[i].to];
for (int i=0; i&num_nodes; ++i)
if (indegree[i] == 0) Q.push(i);
while (!Q.empty()) {
int w = Q.front();
for (int i=0; i&G[w].size(); ++i) {
if (d[edges[G[w][i]].to] & d[w] + edges[G[w][i]].weight && d[w] != __inf) {
d[edges[G[w][i]].to] = d[w] + edges[G[w][i]].weight;
p[edges[G[w][i]].to] = G[w][i];
if (--indegree[edges[G[w][i]].to] == 0)
Q.push(edges[G[w][i]].to);
}Floyd-Warshall与前面四种不同，Floyd-Warshall 算法是所谓的「全源最短路径」，也就是任意两点间的最短路径。它并不是对单源最短路径$\mid V\mid$次迭代的一种渐进改进，但是对非常稠密的图却可能更快，因为它的循环更加紧凑。而且，这个算法支持负的权值。Floyd-Warshall 算法如下：int dist[max_nodes][max_nodes]; // 记录路径长
int path[max_nodes][max_nodes]; // 记录实际路径
bool Floyd_Warshall()
for (int i=0; i&num_nodes; ++i)
for (int j=0; j&num_nodes; ++j)
path[i][j] = j;
for (int k=0; k&num_nodes; ++k) {
for (int i=0; i&num_nodes; ++i) {
for (int j=0; j&num_nodes; ++j) {
if (dist[i][j] & dist[i][k] + dist[k][j]
&& dist[i][k] != __inf && dist[k][j] != __inf) {
dist[i][j] = dist[i][k] + dist[k][j];
path[i][j] = path[i][k];
if (i == j && dist[i][j] & 0)
return false;
return true;
}其中 dist 数组应初始化为邻接矩阵。需要提醒的是， dist[i][i] 实际上表示「从顶点 i 绕一圈再回来的最短路径」，因此图存在负环当且仅当 dist[i][i]&0。初始化时， dist[i][i]可以初始化为0，也可以初始化为$\infty$ 。显示实际路径显示实际路径实际上非常简单。利用前四个算法提供的 int *p，还原实际路径的一个方法如下：void printpath(int from, int to, bool firstcall = true)
if (from == to) {
printf(&%d&, from);
if (p[to] == -1) return;
if (firstcall) printf(&%d -&&, from);
int v = edges[p[to]].from;
if (v == from) {
if (firstcall) printf(& %d&, to);
printpath(from, v, false);
printf(& %d -&&, v+1);
if (firstcall) printf(& %d&, to);
}利用 Floyd-Warshall 算法提供的 int **path，还原实际路径的一个方法如下：void showpath(int from, int to)
int c = from;
printf(&%d -& %d:(%2d)
%d&, from, to, dist[from][to], from);
while (c != to) {
printf(& -& %d&, path[c][to]);
c = path[c][to];
printf(&\n&);
}&来自话题&&/&&/&&/&&/&相关文章讨论Please enable JavaScript to view the comments powered by Disqus.