如何测试加权图是否有负循环

Question

我需要创建一个测试，如果作为参数的图（有向图）具有负权重循环，则 returns 为真，否则为假。

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

//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

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

如果你在节点 F 中找到一个圆，你可以通过向上遍历树来计算圆的总权重，直到你再次找到 F，然后对权重求和。

当然确定了圆的大小，并且是正的，还要继续BFS遍历，但是不遍历F的children。如果它是负数，return 来自函数，因为你发现了一个负圆。

编辑：您还可以在 BFS 遍历步骤中跟踪当前的总权重，这样您就不必向上遍历树来计算总权重...因为您的图形是有向的，所以方法也更适合...

Answer 2

你必须应用 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[]

如何测试加权图是否有负循环

How to test if a weighted graph has a negative cycle

java

graph

bellman-ford