如何检验一个加权图是否有负循环

Question

我需要创建一个测试，如果图(有向图)作为参数具有负权重的循环，则返回true，否则返回false。

现在我创建了这个。理论上应该检查是否存在"一般"循环，而不是是否存在负循环。我怎样才能改变方法?有更简单的还是更有效的?

//if there is a negative cycle, get out and return 
public void bellmanFord(Graph<V, E> graph, V source, V dest) {
    ArrayList<V> vertices = (ArrayList<V>) graph.getVertices();
    HashMap<V, Boolean> visited = new HashMap<V, Boolean>(vertices.size());
    for(V v : vertices) { 
        visited.put(v, false);
    }
    boolean cycle = hasNegativeCycle(graph, source, visited, vertices);
    if(cycle == true)
        return;
    else {
        ...
    }
}
public boolean hasNegativeCycle(Graph<V, E> graph, V source, HashMap<V, Boolean> visited, ArrayList<V> vertices) {
    visited.put(source, true);
    for(V u : vertices) {
      ArrayList<V> neigh_u = (ArrayList<V>) graph.getNeighbors(u);
      for(V v : neigh_u) {
        if(visited.get(v) == true || hasNegativeCycle(graph, v, visited, vertices)) {
          return true;
        }
      }
    }
    return false;
}

感谢

---

编辑:正如你可以从上面写的方法名看到的，我正试图实现Bellman-Ford算法，我遵循这个伪代码:

BellmanFord(Graph G, Vertex start) { 
    foreach(Vertex u of G) { 
        dist[u] = ∞; 
        prev[u] = -1; 
    } 
    prev[start] = s; 
    dist[start] = 0; 
    repeat n times { 
        foreach(Vertex u of G) { 
            foreach(Vertex v near u) { 
                if(dist[u] + weigth_uv < dist[v]) { 
                    prev[v] = u; 
                    dist[v] = dist[u] + weigth_uv; 
                } 
            } 
        } 
    } 
}

Answer 1

必须应用Bellman-Ford算法。Wikipedia具有适当的伪代码。如果你正确地使用这个方法，你的问题就会解决。

function BellmanFord(list vertices, list edges, vertex source)
   ::distance[],predecessor[]
   // This implementation takes in a graph, represented as
   // lists of vertices and edges, and fills two arrays
   // (distance and predecessor) with shortest-path
   // (less cost/distance/metric) information
   // Step 1: initialize graph
   for each vertex v in vertices:
       if v is source then distance[v] := 0
       else distance[v] := inf
       predecessor[v] := null
   // Step 2: relax edges repeatedly
   for i from 1 to size(vertices)-1:
       for each edge (u, v) in Graph with weight w in edges:
           if distance[u] + w < distance[v]:
               distance[v] := distance[u] + w
               predecessor[v] := u
   // Step 3: check for negative-weight cycles
   for each edge (u, v) in Graph with weight w in edges:
       if distance[u] + w < distance[v]:
           error "Graph contains a negative-weight cycle"
   return distance[], predecessor[]

Answer 2

您可能想要对图进行BFS遍历。在每个节点访问时，记录节点的唯一id(例如，如果实现了。hashcode())到HashSet中。每当您试图将一个已经存在的元素插入哈希集时，您都会发现一个圆圈。

如果你在节点F找到了一个圆圈，你可以通过向上遍历树来计算圆圈的总权重，直到你再次找到F，并将权重相加。

当然，在确定圆的大小之后，如果它是正的，你必须继续BFS遍历，但是不遍历F的子节点。如果它是负的，从函数返回，因为你发现了一个负的圆。

编辑:您还可以在BFS遍历步骤期间跟踪当前的总权重，这样您就不必向上遍历树来计算总权重…当你的图形是有向的，这种方法也会更适合…