//由于Dijksrta算法，当图中的权值边含有负值时，求不出最短路 //原因是因为，每个结点只能入队一次，被访问过后永久标记，所以，当存在一条负的权值边 //使得某一个节点到源点s的距离更短时，无法再一次调用此结点更新其余的点 //所以下面介绍另外的两种算法 //Bellman-Ford算法：如果存在一条最短路，一定不存在环 //如果有环，则环程序会在环中循环，无法跑出来，如果存在最短路，一定没有负环 //因为一直在负环当中跑，最短路的路径会一直减小，没有一个最小值 //下面先上代码：（有一些地方还没明白，只能先盲敲一遍了） bool bellman ford(int s) { queue<int> Q; memset(inq,0,sizeof(inq));//inq数组记录结点有没有被访问过 memset(cnt,0;sizeof(cnt));//cnt数组记录每一个结点出现的次数，由于负边的存在，一个结点可被访问多次 //如果某一个结点被访问的次数大于n，则一定说明一定含有环 for(int i=0;i<n;i++) d[i]=inf; d[s]=0; inq[s]=true; Q.push(s); while(!Q.empty()) { int u=Q.front(); Q.pop(); inq[u]=false; for(int i=0;i<G.size();i++) Edge& e=edges[G[u][i]]; if(d[u]<inf&&d[e.to]>d[u]+e.dist) { d[e.to]=d[u]+e.dist; p[e.to]=G[u][i]; if(!inq[e.to]) { Q.push(e.to) inq[e.to]=true; if(++cnt[e.to]>n) return false; } } } return true; } //Floy算法时间复杂度O（n*n*n),基于动态规划 for(int k=0;k<n;k++) for(int i=;i<n;i++) for(int j=0;j<n;j++) d[i][j]=min(d[i][j],d[i][k]+d[k][j]); //如果不关心路径的长度，而只要路径是否连通 //则代码改写成d[i][j]=d[i][j]||(d[i][k]&&d[k][j]) //初始化时，初始化d[i][j]为inf要注意