Bellman-Ford negative cycle predecessor does not exist

Question

I have implemented the Bellman-Ford algorithm to detect negative cycles in a graph. It is worth noting that each edge in the graph has an inverse, so if an edge exists that can go from A -> B, there also exists an edge that can go from B -> A.

My problem is when I am navigating the predecessor chain (stored in the dictionary pred). It seems that the source vertex never has a predecessor, so when I am looping through each vertex in the negative cycle check, an exception is thrown because pred never has an entry for the source vertex.

What does this mean? There seems to be a negative cycle in the graph, but if nothing precedes the source vertex, and the source vertex is "included" in the detected negative cycle, is there really a cycle to begin with?

private List<Vertex> BellmanFord( Vertex source )
{
  var dist = new Dictionary<Vertex, double>();
  var pred = new Dictionary<Vertex, Vertex>();

  // Initialize
  foreach( var vertex in Vertices )
    dist[ vertex ] = double.MaxValue;
  dist[ source ] = 0;

  // Relax
  foreach( var vertex in Vertices )
    foreach( var edge in Edges )
      Relax( edge, ref dist, ref pred );

  // Check for negative cycles
  foreach( var edge in Edges )
  {
    if( dist[ edge.From ] != double.MaxValue )
      if( HasCycle( edge, ref dist )
      {
        var cycle = new List<Vertex>();
        var vertex = edge.From;

        while( vertex == edge.To )
        {
          cycle.Add( vertex );
          vertex = pred[ vertex ];
        }

        cycle.Add( edge.To );
        return cycle;
      }
  }

  return new List<Vertex>(); // No cycle
}

private void Relax( Edge edge, ref Dictionary<Vertex, double> dist, ref Dictionary<Vertex,Vertex> pred )
{
  if( dist[edge.From] == double.MaxValue )
    return;

  var newDist = dist[ edge.From ] + edge.Weight;
  if( newDist < dist[ edge.To] )
  {
    dist[ edge.To ] = newDist;
    pred[ edge.To ] = edge.From;
  }
}

private bool HasCycle( Edge edge, ref Dictionary<Vertex, double> dist )
{
  return dist[edge.To] > dist[edge.From] + edge.Weight;
}

And for good measure, the weight of each edge is calculated as -1 * Math.Log( value ).

Codor Codor · Accepted Answer · 2019-03-29T15:48:08

To my understanding, the observed behaviour does not indicate a bug in your implementation. The Bellman-Ford algorithm is able to conclude that there is a cycle of negative length; this does not mean that every cycle of negative length can be found. The Floyd-Warshall algorithm might be more suitable for that. Both algorithms solve different formulations of the problem; the first one solves the single-source shortest path problem while the second one solved the all-pairs shotest path problem.

Bellman-Ford negative cycle predecessor does not exist

1 Answers