1.算法标签

2.算法概念

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一节中的例子):

单源最短路径的Bellman-Ford 算法-LMLPHP

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

 

示例输出:

单源最短路径的Bellman-Ford 算法-LMLPHP

05-02 18:45
查看更多