贝尔曼-福特负周期前身不存在

Question

我已经实现了Bellman-Ford算法来检测图中的负循环。值得注意的是，图中的每条边都有一个倒数，因此如果存在一条边，它可以从A开始-

我的问题是在导航前置链时（存储在dictionarypred中）。源顶点似乎从来没有前置顶点，因此当我在负循环检查中循环遍历每个顶点时，会引发异常，因为pred从来没有源顶点的条目。

这是什么意思？图中似乎有一个负循环，但是如果没有任何东西先于源顶点，并且源顶点被“包括”在检测到的负循环中，那么真的有一个循环可以开始吗？

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。日志（值）。




Answer 1

据我所知，观察到的行为并不表明您的实现中存在缺陷。Bellman-Ford算法能够得出结论，存在一个负长度的循环；这并不意味着可以找到每一个负长度的循环。Floyd-Warshall算法可能更适合这种情况。两种算法解决问题的不同公式；第一种方法解决了单源最短路径问题，第二种方法解决了全对最短路径问题。