Предшественник отрицательного цикла Беллмана-Форда не существует - PullRequest
Новая
       24

Предшественник отрицательного цикла Беллмана-Форда не существует

1 голос
/ 29 марта 2019

Я реализовал алгоритм Беллмана-Форда для обнаружения отрицательных циклов на графике. Стоит отметить, что каждое ребро в графе имеет инверсию, поэтому, если существует ребро, которое может идти от A -> B, также существует ребро, которое может идти от B -> A.

Моя проблема заключается в навигации по цепочке предшественников (хранится в словаре pred). Кажется, что исходная вершина никогда не имеет предшественника , поэтому, когда я зацикливаюсь на каждой вершине в проверке отрицательного цикла, выдается исключение, потому что 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.Log( value ).

1 Ответ

1 голос
/ 29 марта 2019

Насколько я понимаю, наблюдаемое поведение не указывает на ошибку в вашей реализации.Алгоритм Беллмана-Форда может заключить, что существует цикл отрицательной длины;это не означает, что каждый цикл отрицательной длины может быть найден. Алгоритм Флойд-Варшалла может быть более подходящим для этого.Оба алгоритма решают разные постановки задачи;первая решает проблему кратчайшего пути из одного источника, а вторая решает проблему кратчайшего пути из всех пар.

...