1.算法标签
BFS
2.算法概念
Bellman-Ford算法有这么一个先验知识在里面，那就是最短路径至多在N步之内，其中N为节点数，否则说明图中有负权值的回路，这样的图是找不到最短路径的。因此Bellman-Ford算法的思想如下，进行N次循环，在第 k 次循环中用dist数组记录 k 步之内到达各个顶点的最短路径长度，记做distk,然后在第k+1次循环中，遍历每条边，若有dist[v]>dist[u]+cost[u][v],则更新distk+1[v]=dist[u]+cost[u][v],并将v节点的前驱节点记为u。因此这是一个广度优先的算法，如果N次循环之后发现还未收敛，说明有负权值的回路，说明找不到最短路径。正因为如此，Bellman-Ford算法适应性比较强，但是算法复杂度较高，为O(VE),不过，经过优化的Bellman-Ford算法效率能有明显的提升。
Bellman-Ford算法维持一下几个数据结构：
- dist数组 ：第 k 次循环中用dist数组记录 k 步之内到达各个顶点的最短路径长度
- previous数组 ： 记录当前前驱
3.代码实现
头文件：
/*
areslipan@163.com
filename: Bellman_Ford.h
*/
#ifndef _BELLMAN_FORD_
#define _BELLMAN_FORD_
#include "graph.h"
#include <iostream>
bool BellmanFord(GraphAdjList *g,int start,vector<int> & previous);
#endif
|
/*
areslipan@163.com
filename : Bellman_Ford.cpp
*/
#include "Bellman_Ford.h"
using namespace std;
bool BellmanFord(GraphAdjList *g,int start,vector<int> & previous)
{
vector<int>dist(g->numNodes,MYINF);
vector<int>path(g->numNodes,-1);
previous=path;
dist[start]=0;
for(int i=0;i<g->numNodes;++i)
{
//遍历邻接表中的每条边，进行松弛操作
for(int j=0;j<g->numNodes;++j)
{
EdgeNode * cur=g->adjList[j].firstedge;
while(cur!=NULL)
{
//找到一条k+1步之内可达的比当前路径更短的路径
if(cur->weight+dist[j] < dist[cur->adjvex])
{
dist[cur->adjvex]= cur->weight+dist[j];
previous[cur->adjvex]=j; //记录前驱
}
cur=cur->next;
}
}
}
for(int j=0;j<g->numNodes;++j)
{
EdgeNode * cur=g->adjList[j].firstedge;
while(cur!=NULL)
{
if(cur->weight+dist[j] < dist[cur->adjvex])return false;
cur=cur->next;
}
}
return true;
}
|
测试文件：
/*
areslipan@163.com
filename : testBellmanFord.cpp
*/
#include "Bellman_Ford.h"
#include "graph.h"
using namespace std;
int main()
{
GraphAdjList g;
create_adjlist_graph(&g);
show_adjlist_graph(&g);
vector<int>previous;
while(true)
{
cout<<"input start and end: ";
int start ; int end;
cin>>start>>end;
if(start==-1)break;
if(BellmanFord(&g,start,previous))
{
show_path(previous,start,end);
}
else cout<<"Negative circle exists"<<endl;
}
destroy_adjlist_graph(&g);
show_adjlist_graph(&g);
system("pause");
}
|
示例输入（同Dijkstra一节中的例子）：
6 18
0 1 2 3 4 5
0 1 1
1 0 1
0 2 4
2 0 4
1 2 2
2 1 2
1 4 5
4 1 5
1 3 7
3 1 7
2 4 1
4 2 1
3 4 3
4 3 3
3 5 2
5 3 2
4 5 6
5 4 6
0 5
|
示例输出：
