一、介绍：
/wiki/Bellman%E2%80%93Ford_algorithm
二、维基上的伪代码：
function BellmanFord(list vertices, list edges, vertex source)::distance[],predecessor[]// This implementation takes in a graph, represented as// lists of vertices and edges, and fills two arrays// (distance and predecessor) about the shortest path// from the source to each vertex// Step 1: initialize graphfor each vertex v in vertices:distance[v] := inf // Initialize the distance to all vertices to infinitypredecessor[v] := null // And having a null predecessordistance[source] := 0 // The distance from the source to itself is, of course, zero// Step 2: relax edges repeatedlyfor i from 1 to size(vertices)-1: //just |V|-1 repetitions; i is never referencedfor each edge (u, v) with weight w in edges:if distance[u] + w < distance[v]:distance[v] := distance[u] + wpredecessor[v] := u// Step 3: check for negative-weight cyclesfor each edge (u, v) with weight w in edges:if distance[u] + w < distance[v]:error "Graph contains a negative-weight cycle"return distance[], predecessor[]
三、C++代码：
实现1:图用边集合存储O(VE)
#include<iostream>#include<vector>#define INF 9999999 using namespace std;
class Graph{class Edge{public:int src;int dest;double weight;Edge(int _src,int _dest,double _weight){src = _src;dest = _dest;weight = _weight;}};vector<Edge> edges;int V;//顶点数 int E;//边数 void printSolution(vector<double> &dist,vector<int>&parent, vector<double>&weights); public:Graph(int _V){V = _V;E = 0; }void BellmanFord(int src);void addEdge(int u,int v,double weight);};
void Graph::addEdge(int u,int v,double weight){Edge newEdge(u,v,weight);edges.push_back(newEdge);E++;//边数不定死了}
void Graph::BellmanFord(int src){vector<double>dist(V,INF); vector<int>parents(V,src); //双亲数组 vector<double>weights(V,INF); //weight of u -> v dist[src] = 0;weights[src]=0; //松弛所有的边 |V|-1次，简单的(没有回路的)最短路//径(从src到其他点),最多只有 |V|-1条边可以松弛 for(int i = 1; i < V; i++){for(int j = 0; j < E; j++){int u = edges[j].src;int v = edges[j].dest;double weight = edges[j].weight;if(dist[u] + weight < dist[v]){dist[v] = dist[u] + weight;parents[v] = u;weights[v] = weight; //weight of u -> v} }}//再检查一次，如果还能松弛，说明有负值循环 for(int i = 0; i < E; i++){int u = edges[i].src;int v = edges[i].dest;double weight = edges[i].weight;if(dist[u] + weight < dist[v]){cout<<"graph contains a negative-weight cycle"<<endl; } }printSolution(dist, parents,weights);};
void Graph::printSolution(vector<double> &dist,vector<int>&parent,vector<double>&weights){for(int i = 0; i < V; i++){cout<<parent[i]<<" --> " <<i<<"\t weights :";(weights[i] == INF) ? cout<<"INF\t" : cout<<weights[i]<<"\t";cout<<"dist["<<i<<"]: ";(dist[i] == INF) ? cout<<"INF"<<endl : cout<<dist[i]<<endl;}}
int main(){/*Graph g(5); g.addEdge(0, 1, -1); g.addEdge(0, 2, 4); g.addEdge(1, 2, 3); g.addEdge(1, 3, 2); g.addEdge(1, 4, 2); g.addEdge(3, 2, 5); g.addEdge(3, 1, 1); g.addEdge(4, 3, -3);*/Graph g(6); g.addEdge(0, 1, 5); g.addEdge(0, 2, 3); g.addEdge(1, 3, 6); g.addEdge(1, 2, 2); g.addEdge(2, 4, 4); g.addEdge(2, 5, 2); g.addEdge(2, 3, 7); g.addEdge(3, 4, -1); g.addEdge(4, 5, -2);g.BellmanFord(1);return 0;}
输出：
实现2：图用邻接表存储O(V*V*E)(邻接矩阵O(V<sup>3</sup>))
#include<iostream>#include<list>#include<set>#include<vector>#define INF 9999999 using namespace std;class Graph{int V;//顶点数list<pair<int,double> > *adj;void printSolution(vector<double> &dist,vector<int>&parents, vector<double>&weights);public:Graph(int _v){V = _v;adj = new list<pair<int,double> >[_v];}~Graph(){delete [] adj;} void addEdge(int u,int v,int weight){adj[u].push_back(make_pair(v,weight));}void BellmanFord(int src);} ;
void Graph::printSolution(vector<double> &dist,vector<int>&parents,vector<double>&weights){for(int i = 0; i < V; i++){cout<<parents[i]<<" --> " <<i<<"\t weights :";(weights[i] == INF) ? cout<<"INF\t" : cout<<weights[i]<<"\t";cout<<"dist["<<i<<"]: ";(dist[i] == INF) ? cout<<"INF"<<endl : cout<<dist[i]<<endl;}}
void Graph::BellmanFord(int src){vector<double>dist(V, INF);vector<double>weights(V,INF);//weights[v]记录从src到v分支上某点到v的最小权值vector<int>parents(V,src); dist[src] = 0;weights[src] = 0; //步骤1:松弛所有的边 |V|-1次，简单的(没有回路的)最短路//径(从src到其他点),最多只有 |V|-1条边可以松弛for(int k = 1; k < V; k++){for(int u = 0; u < V; u++){list<pair<int,double> >::iterator it;for(it = adj[u].begin(); it != adj[u].end(); it++){int v = it->first;double weight = it->second;if(dist[u]+weight < dist[v]){dist[v] = dist[u]+weight;parents[v] = u; weights[v] = weight;}} }}//步骤2：再检查一次，如果还能松弛，说明有负值循环 for(int u = 0; u < V; u++){list<pair<int,double> >::iterator it;for(it = adj[u].begin(); it != adj[u].end(); it++){int v = it->first;double weight = it->second;if(dist[u]+weight < dist[v]){cout<<"the graph contains negative weight cycle";return ;}} }printSolution(dist, parents, weights);}
int main(){/*Graph g(5); g.addEdge(0, 1, -1); g.addEdge(0, 2, 4); g.addEdge(1, 2, 3); g.addEdge(1, 3, 2); g.addEdge(1, 4, 2); g.addEdge(3, 2, 5); g.addEdge(3, 1, 1); g.addEdge(4, 3, -3);*/Graph g(6); g.addEdge(0, 1, 5); g.addEdge(0, 2, 3); g.addEdge(1, 3, 6); g.addEdge(1, 2, 2); g.addEdge(2, 4, 4); g.addEdge(2, 5, 2); g.addEdge(2, 3, 7); g.addEdge(3, 4, -1); g.addEdge(4, 5, -2);g.BellmanFord(1);return 0;}
