1.算法标签

BFS

2.算法概念

Bellman-Ford算法有这么一个先验知识在里面，那就是最短路径至多在N步之内，其中N为节点数，否则说明图中有负权值的回路，这样的图是找不到最短路径的。因此Bellman-Ford算法的思想如下，进行N次循环，在第 k 次循环中用dist数组记录 k 步之内到达各个顶点的最短路径长度，记做dist^k,然后在第k+1次循环中，遍历每条边，若有dist[v]>dist[u]+cost[u][v],则更新dist^k+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 
         
           bool BellmanFord(GraphAdjList *g,int start,vector
          
            & previous); #endif
          
         

 

/*     areslipan@163.com     filename : Bellman_Ford.cpp */ #include "Bellman_Ford.h" using namespace std; bool BellmanFord(GraphAdjList *g,int start,vector
         
           & previous) {
           vector
          
           dist(g->numNodes,MYINF);     vector
           
            path(g->numNodes,-1);     previous=path;     dist[start]=0; for(int i=0;i
            
             numNodes;++i)     {
       //遍历邻接表中的每条边，进行松弛操作 for(int j=0;j
             
              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
              
               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
         
          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"<
         

 

示例输入（同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

 

示例输出：