Data Structures, Algorithms, & Applications in C++
Single Source Shortest Paths
With Negative Edge Costs

Graphs/digraphs With Negative Edge Costs

Dynamic Programming Formulation

Pseudocode

initialize d^1;
// compute remaining d^k's
for (int k = 2; k < n; k++) {
   d^k(v) = infinity for all v;
   for (each edge (u,v))
      d^k(v) = min(d^k(v), d^(k-1)(u) + cost(u,v));
   }

Refinements To Pseudocode

initialize d() = d^1;
// compute d^(n-1)
for (int k = 2; k < n; k++)
   for (each edge (u,v))
      d(v) = min(d(v), d(u) + cost(u,v));

initialize d() = d^1;
put the vertices that are adjacent from the source vertex onto a list C1;
// compute d^(n-1)
for (int k = 2; k < n; k++) {
   // see if there are vertices whose d value has changed
   if (C1 is empty) break;  // no such vertex
   while (C1 is not empty) {
      delete a vertex u from C1;
      for (each edge (u,v)) {
         d(v) = min(d(v), d(u) + cost(u,v));
         if d(v) has changed and v is not on list C2 add v to list C2;
         }
   swap C1 and C2;
   }
      

C++ Implementation

template <class T>
void WNetwork<T>::BellmanFord(int s, T d[], int p[])
{// Shortest paths from vertex s, return shortest
 // distances in d and predecessor info in p.
 // Graph may have edges with negative cost but should
 // not have a cycle with negative cost.
   int n = Vertices();
   if (s < 1 || s > n) throw OutOfBounds();

   InitializePos();  // init graph iterator array
   // define two chains for vertices whose
   // d has changed
   Chain<int> *C1 = new Chain<T>;
   Chain<int> *C2 = new Chain<T>;
   // define an array to record vertices that are in C2
   bool *InC2 = new bool[n+1];

   // initialize p[1:n] = 0 and InC2[1:n] = false
   for (int i = 0; i <= n; i++) {
      p[i] = 0;
      InC2[i] = false;
      }
   p[s] = s;

   // initialize d[] = d^1() and C1
   // C1 will contain all vertices adjacent from s
   int u;
   T c;  // edge cost
   First(s, u, c);
   while (u) {
      d[u] = c;
      p[u] = s;
      C1->Insert(0,u);  // insert at front
      Next(s, u, c);
      }
   d[s] = 0;
   
   // do n - 2 rounds of updating d
   for (int k = 2; k < n; k++) {
      if (C1->IsEmpty()) break;  // no more changes possible
      // process vertices on C1
      while (!C1->IsEmpty()) {
         // get a vertex u whose d value has changed
         C1->Delete(1,u);  // delete from front

         // update d for the neighbors v of u
         int v;
         First(u, v, c);
         while (v) {
            if (!p[v] || d[u] + c < d[v]) {
               // this is either the first path to v
               // or is a shorter path than earlier ones
               d[v] = d[u] + c;
               p[v] = u;
               if (!InC2[v]) {
                  C2->Insert(0,v);
                  InC2[v] = true;
                  }
               }
            Next(u, v, c);
            }
         }

      // swap C1 and C2 for next update round
      Swap(C1, C2);

      // reset InC2[1:n] to false
      ChainIterator<int> c2;
      int *w = c2.Initialize(*C1);
      while (w) {
         InC2[*w] = false;
         w = c2.Next();
         }
      }

   delete C1;
   delete C2;
   DeactivatePos();
}

Complexity Analysis

Difference Equations

1. The weighted digraph has one vertex for each variable plus an additional vertex.
2. There is a directed edge from this additional vertex to each of the remaining vertices. The weight of each of these edges is zero.
3. For each equation x_i - x_j <= c_q, there is a directed edge from the vertex that represents x_j to the one that represents x_i The weight of this edge is c_q.

1. The constructed digraph has a negative-length cycle iff the system of difference equations it is constructed from has no solution.
2. If the system has a solution, then the lengths of the shortest paths from the additional vertex to the remaining vertices defines a solution.

1. Suppose that the constructed digraph has a negative-length cycle C. Without loss of generality, we may assume that this cycle is 1, 2, 3, ..., u, 1 where vertex i represents variable x_i, 1 <= i <= u. Note that the additional vertex is on no cycle because it has no incoming edge. The edge (i,i+1) represents the equation x_i+1 - x_i <= cost(i,i+1), and the edge (u,1) represents the equation x₁ - x_u <= cost(u,1). Adding up both sides of the equations represented by the edges on the negative-length cycle C, we see that all variables cancel out on the left side to yield a left-side sum of zero. The sum of the right sides is the sum of the edge costs on the cycle. Since this sum is negative, adding the equations yields the equation 0 <= sum of edge costs < 0 which is a false statement. Therefore, no assignment to the x_is can satisfy the given equations.
   
   The fact that if the system has no solution then the digraph has a negative-length cycle is established in a similar way.
2. We may assume the digraph has no negative-length cycle. Consequently, there is a shortest path from the additional vertex to each of the remaining vertices. Let d(i) be the length of the shortest path from the additional vertex to the vertex i that represents variable x_i. Let x_i-x_j <= c_q be any equation in the given system. From the definition of d() it follows that d(i) <= d(j) + cost(j,i) = d(j) + c_q. Therefore, d(i) - d(j) <= c_q. Hence setting x_i = d(i) for all i results in an assignment that satisfies all equations.