可以解决有负权边的图，但不能解决有负权回路的图(有负权回路的最短路本来就不存在嘛)
思路：
假设一共有n个点
那么从u~v最多经过n-1个点便肯定能找出最短边(因为最多把其他的点全走一遍就知道最短路径了)
所以算法就是：
从u(起点)出发，经过1个点到v点试试，如果更加小，就更新一下dist
再经过2个点到v点试试，如果更加小，就更新一下dist
.........
当经过n-1个点时，此时dist中就是从u点出发到各点的最短路径
判断有无负权回路的方法：
再试着从u点出发，更新所有其他点的dist，如果能更新就肯定有负权环
因为此时u点到v点经过了n个点，肯定有个点是经过2次的，而经过这个点2从比经过1次路径更加短，所以肯定有负权环
代码如下：
#include<iostream> #include<cstdio> #include<vector> #include<algorithm> using namespace std; const int INF=(1<<30); const int maxn=1000+5; struct Edge{ int from,to,weight; Edge(int f,int t,int w):from(f),to(t),weight(w){} }; vector<Edge> edges; int dist[maxn]; bool Bellman_ford(int s,int n) { for(int i=0;i<n;i++) dist[i]=INF; dist[s]=0; for(int k=1;k<n;k++) //从u~v点经过k条边 for(int i=0;i<edges.size();i++) { int u=edges[i].from; int v=edges[i].to; int w=edges[i].weight; dist[v]=min(dist[v],dist[u]+w); } for(int i=0;i<edges.size();i++){ //判断有无负环 int u=edges[i].from; int v=edges[i].to; int w=edges[i].weight; if(dist[v]>dist[u]+w) return true; } return false; } int main() { int T; cin>>T; while(T--) { int N,M; cin>>N>>M; //M条边 int u,v,w; edges.clear(); while(M--) { cin>>u>>v>>w; edges.push_back(Edge(u,v,w)); edges.push_back(Edge(v,u,w)); } cout<<(Bellman_ford(1,N)?"YES":"NO")<<endl; //判断有无负环 } return 0; }
