C# 中的 Bellman Ford：总是 returns 负循环。我错过了什么吗？

Question

这是实现：

Returns 如果没有负循环则为真

    public static bool ShortestPaths(Graph graph, int vStart,
        out double[] pi, out int[] pred)
    {
        int V = graph.Nodes();
        pi = new double[V];                 //shortest known path lengths
        pred = new int[V];                  //predeceesor nodes for these paths
        for (int v = 0; v < V; v++){
            // TODO: Here we need to initialize pi and pred.
            pi[v] = System.Double.PositiveInfinity;
            pred[v] = -1;
        }
        pi[vStart] = 0;
        List<Edge> edges = graph.AllEdges();
        // Apply the inner loop once for every node.
        for (int v = 0; v < V; v++)
        {   
            foreach (Edge edge in edges)    //test edges all edges
            {
                // TODO: In this inner loop we need to update
                //       pi and pred.
                int w = edges[v].To();
                double weight = edges[v].Weight();
                if (pi[v] + weight < pi[w]) { 
                    pi[w] = pi[v] + weight;
                    pred[w] = v; 
                }
            }
        }

测试是否存在负循环，returnfalse 如果存在这样的循环。

        List<Edge> bedges = graph.AllEdges();
        foreach (Edge edge in bedges) {
            int w = edge.To();
            int v = edge.From();
            double weight = edge.Weight();
            if (pi[v] + weight < pi[w]) {
                return false;
            }
        }
        return true;
    }

图形如下所示：(v,w,weigth)

        int[,] edges = 
        {{0,1,3},{0,2,2},{0,3,3},{1,0,8},{1,3,2},{1,4,1},{2,0,7},{2,5,2},{2,6,7},
            {3,0,6},{3,1,3},{3,4,2},{3,5,3},{3,6,4},{4,1,1},{4,3,3},{4,6,1},{5,2,3},
            {5,3,3},{5,6,3},{6,3,3},{6,4,1},{6,2,7},{6,5,4}};

这里没有负整数，但它会 return false。

Answer 1

您的放松步骤有错误：

你的外循环指定顶点v。

你的内循环指定边e。

在你的内部循环中，你在每次迭代中重复使用边缘 v，而不是考虑边缘 e 来填充你的 pi 和 pred 数组。

您可以按如下方式修复：

for (int v = 0; v < V; v++)
{   
    foreach (Edge edge in edges)    //test edges all edges
    {
        int from = edge.From();
        int to = edge.To();
        double weight = edge.Weight();
        if (pi[from] + weight < pi[to]) { 
            pi[to] = pi[from] + weight;
            pred[to] = from; 
        }
    }
}

C# 中的 Bellman Ford：总是 returns 负循环。我错过了什么吗？

Bellmanford in C# : Always returns negative cycle. Am I missing somthing?

c#

bellman-ford