本文使用C++实现了这一基本算法。参考《算法导论》第24.1节

    笔者使用了vector实现邻接链表，以提高运行效率。

/** * Bellman-Ford's Single Source Shortest Path Algorithm in C++ * Time Cost : O(|N||M|) * Introduction to Algorithms (CLRS) 24.1 * Author: Zheng Chen / Arclabs001 * Copyright 2015 Xi'an University of Posts & Telecommunications */#include 
    
     #include 
     
      #include 
      
       #define INF 0xfffffffusing namespace std;const int N = 5;const int M = 10;ifstream in;struct edge{    int dest;    int weight;};struct vertex{    int num;    int dist;    int inDegree,outDegree;    vertex * parent;}V[N];vector
       
         AdjList[N];bool changes; //To check if there is changes in the loop//Suppose the longest way has m edges, so the distance will not change after//m loops, so that we can terminate the loop after m+1 times.void initialize(int s){    for(int i=0; i
        
         
          >_start>>_dest>>_weight;        tmp->dest = _dest;        tmp->weight = _weight;        V[_start].outDegree++;        V[_dest].inDegree++;        AdjList[_start].push_back(*tmp);    }    V[s].dist = 0;}void relax(int u, int v, int weight)  //The "relax" operation{    if(V[v].dist > V[u].dist + weight)    {        V[v].dist = V[u].dist + weight;        V[v].parent = &V[u];        changes = true;    }}bool bellman_ford(int s){    changes = true;    initialize(s);    for(int k=1; k
          
            V[i].dist + tmp.weight)                return false;        }    }    return true;}int main(){    in.open("Bellman_Ford.txt");    if(bellman_ford(0))    {        cout<<"Succeed ! The distance of each vertex are :"<
           
            
             <
             
              <<" ";        }        cout<
              
               <<"Their parents are :";        for(int i=1; i
               
                <
                
                 num<<" ";        }    }    else    {        cout<<"Failed ! There are at least one negative circle !"<
                 
                   u.d + w(u,v))        v.d = u.d + w(u,v)        v.parent = u}Bellman-Ford(G,w,s){    Initialize-Single-Source(G,s)    for i=1 to |G.V|-1        for each vertex (u,v) in G.E            Relax(v,u,w)    for each edge (u,v) in G.E        if(v.d > u.d + w(u,v))            return FALSE    return TRUE}*/
                 
                
               
              
             
            
           
          
         
        
       
      
     
    

//Bellma-Ford文件内容如下：

0 1 6

0 3 7

1 2 5

1 3 8

1 4 -4

2 1 -2

3 2 -3

3 4 9

4 2 7

4 0 2

每一行的三个元素分别表示某条边的起始节点、终止节点、这条边的权重。