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

Question

This is the impelemtation:

Returns true if there is no negative cycle

    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; 
                }
            }
        }

Test whether there is a negative cycle and return false if such a cycle exists.

        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;
    }

graphes look like this: (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}};

There is no negative int in this but it will return false.

Answer 1

You have a bug in your relaxation step:

Your outer loop specifies vertex v.

Your inner loop specifies edge e.

Inside your inner loop, you're repeatedly taking edge v for each iteration instead of considering edge e to fill your pi and pred arrays.

You can fix it as follows:

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; 
        }
    }
}