Bellman-Ford算法

/* Bellman-Ford算法伪代码： for(i=0;i<n-1;i++)//执行n-1轮操作，其中n为顶点数 { for(each edge u->v)//每轮操作都遍历所有边 { if(d[u]+length[u->v]<d[v])//以u为中介点可以使d[v]更小 { d[v] = d[u] + length[u->v];//松弛操作 } } } for(each edge u->v)//对每条边进行判断 { if(d[u] + length[u->v]<d[v])//如果仍可以被松弛 { return false;//说明图中有从源点可达的负环 } } return true; */ //下面是完整Bellman-ford算法的代码，图是邻接表形式，时间复杂度为O(VE) //若是邻接矩阵形式，时间复杂度会到O(V^3) #include<vector> #include<algorithm> using namespace std; const int MAXV = 1000; const int INF = 1000000000; struct Node { int v, dis;//v为邻接边的目标顶点，dis为邻接边的边权 }; vector<Node> Adj[MAXV];//图G的邻接表 int n;//n为顶点数，MAXV为最大顶点数 int d[MAXV];//起点到达各点的最短路径长度 bool Bellman(int s)//s为源点 { fill(d, d + MAXV, INF); d[s] = 0;//起点s到达自身的距离为0 //以下为求解数组d的部分 for (int i = 0; i < n - 1; i++)//执行n-1轮操作，n为顶点数 { for (int u = 0; u < n; u++)//每轮操作都遍历所有的边 { for (int j = 0; j < Adj[u].size(); j++) { int v = Adj[u][j].v;//邻接边的顶点 int dis = Adj[u][j].dis;//邻接边的权 if (d[u] + dis < d[v])//以u为中介点可以使d[v]更小 { d[v] = d[u] + dis;//松弛操作 } } } } //以下为判断负环的代码 for (int u = 0; u < n; u++)//对每条边进行判断 { for (int j = 0; j < Adj[u].size(); j++) { int v = Adj[u][j].v;//邻接表的顶点 int dis = Adj[u][j].dis;//邻接边的边权 if (d[u] + dis < d[v])//如果仍可以被松弛 { return false;//说明图中有从源点可达的负环 } } } return true;//数组d的所有值都已经达到最优 } /* 实质是对最短路径树的逐层松弛 */