|
一，Bellman-Ford算法的思想
Bellman-Ford算法（以下简称BF算法），用于解决边的权重可以为负值的单源最短路径，它通过对边进行松弛操作逐渐降低从源结点s到各结点v的最短路径估计值v.d，直到该估计值与实际的最短路径权重δ(s,v）相同。
二，Bellman-Ford算法介绍
准备阶段：一副赋值有向图，每个结点有两个属性：d和π，分别表示从源结点到该结点的最短路径和前驱结点
算法过程：初始化各结点，对每条边进行|V|-1次松弛处理，处理完后检查是否存在环路，返回t/f，算法中有两个重要的证明，一个是为何对每条边进行|V|-1次松弛后能够确保v.d=δ(s,v)，另一个是为何v.d>u.d+w(u.v)时存在环路
（1）为何对每条边进行|V|-1次松弛后能够确保v.d=δ(s,v)?
最坏的情况下，从源结点到一个结点的最短路径需要经过所有结点、所有边，即每条边的最坏情况是需要|V|-1次松弛。
（2）为何v.d>u.d+w(u.v)时存在环路?
因为通过（1）我们知道在经过|V|-1次松弛之后能确保v.d=δ(s,v)，那么v.d应该<=u.d+w(u,v)，不可能出现v.d>u.d+w(u.v)的情况，如果出现只有可能存在环路，每次relax都会使v.d无限缩小。
三，Bellman-Ford算法伪代码
在给出BF算法伪代码之前，我们先给出BF算法需要用到的两个方法的伪代码
INITIALIZE_SINGLE_SOURCE(G,s)
1. for each vertex v∈G.V
2. v.d=∞
3. v.π=NULL
4. s.d=0
RELAX(u,v,w)
1. if v.d>u.d+w(u,v)
2. v.d=u.d+w(u,v)
3. v.π=u
BELLMAN_FORD(G,w,s)
1. INITIALIZE_SINGLE_SOURCE(G,s)
2. for i=1 to |G.V|-1
3. for each edge(u,v)∈G.E
4. RELAX(u,v,w)
5. for each edge(u,v)∈G.E
6. if v.d>u.d+w(u.v)
7. return FALSE
8. return TRUE
第1行，对结点的d和π值进行初始化；第2-4行，我们对每条边进行|V|-1次松弛操作；第5-7行，对每条边进行检查，检查是否存在权值为赋值的环路，如果存在环路，返回false；第8行，返回true，说明存在最短路。
四，Bellman-Ford算法的复杂度
时间复杂度：初始化的时间为O(V)，双重循环的时间为O((V-1)*E)，检查的时间为O(E)，因此总时间为O(V+V*E-E+E)=O((V+1)*E)=O(V*E)
五，Bellman-Ford算法的代码
//解决单源最短路径，权重可为负，返回布尔值表示是否存在一个从源节点可以到达的权重为负的环路，若存在环路，则不能解决，否则给出最短路径和权重
bool Bellman_Ford_Algo(Graph * graph, Node * startNode)
{
Initialize_Single_Source(graph, startNode);//初始化结点的d和π
for (int i = 1; i < graph->getNodeList().size(); i++) {//对图的每条边进行relax，需要进行节点数-1轮
for (int j = 0; j < graph->getEdgeList().size(); j++) {
RELAX(graph->getEdgeList()[j]->getStartNode(), graph->getEdgeList()[j]->getEndNode(), graph->getEdgeList());
}
}
for (int k = 0; k < graph->getEdgeList().size(); k++) {//对每条边检查是否存在权重为负值的环路，若不存在环就应该满足v.distance<=u.distance+u到v的距离
if (graph->getEdgeList()[k]->getEndNode()->getDistance() > graph->getEdgeList()[k]->getStartNode()->getDistance() + graph->getEdgeList()[k]->getDistance())
return false;
}
return true;
}
void Initialize_Single_Source(Graph * graph, Node * startNode)
{
for (int i = 0; i < graph->getNodeList().size(); i++)
{
graph->getNodeList()[i]->setDistance(10000000);
graph->getNodeList()[i]->setPrevNode(NULL);
}
startNode->setDistance(0);
}
void RELAX(Node * u, Node * v, vector<Edge *> edges)
{
Edge *uvedge = NULL;
for (int i = 0; i < edges.size(); i++)
{
if (edges[i]->getStartNode() == u && edges[i]->getEndNode() == v)
{
uvedge = edges[i];
}
}
if (v->getDistance() > u->getDistance() + uvedge->getDistance())
{
v->setDistance(u->getDistance() + uvedge->getDistance());
v->setPrevNode(u);
}
}
| 
转播
