Bellman-Ford 负循环前身不存在

Question

我已经实现了 Bellman-Ford 算法来检测图中的负循环。值得注意的是图中的每条边都有一个逆，所以如果存在一条可以从 A -> B 走的边，那么也存在一条可以从 B -> A.

走的边

我的问题是当我浏览前任链（存储在字典 pred 中）时。似乎 源顶点从来没有前任 ，所以当我在负循环检查中循环遍历每个顶点时，抛出异常，因为 pred 从来没有条目源顶点。

这是什么意思？图中似乎有一个负循环，但是如果源顶点之前没有任何东西，并且在检测到的负循环中源顶点是"included"，那么真的有循环开始吗？

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;
}

为了更好地衡量，每条边的权重计算为 -1 * Math.Log( value )。

Answer 1

据我了解，观察到的行为并不表示您的实施中存在错误。 Bellman-Ford 算法能够断定存在一个负长度的循环；这并不意味着可以找到每个负长度的循环。 Floyd-Warshall algorithm 可能更适合。两种算法都解决了问题的不同表述；第一个解决单源最短路径问题，第二个解决全对最短路径问题。

Bellman-Ford 负循环前身不存在

Bellman-Ford negative cycle predecessor does not exist

c#

graph

bellman-ford