0

我需要创建一个测试，如果作为参数的图（有向图）具有负权循环，则返回 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; 
                } 
            } 
        } 
    } 
}
4

2 回答 2

0

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

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

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

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

于 2015-06-01T20:01:12.303 回答
0

您必须应用贝尔曼-福特算法。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[]
于 2015-06-16T18:45:27.720 回答