Беллманфорд в C #: всегда возвращает отрицательный цикл.Я что-то упустил? - PullRequest
Новая
       18

Беллманфорд в C #: всегда возвращает отрицательный цикл.Я что-то упустил?

0 голосов
/ 23 мая 2018

Это имплементация:

Возвращает истину, если нет отрицательного цикла 

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

Проверить, существует ли отрицательный цикл, и вернуть ложь, если такой цикл существует. 

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

В этом нет отрицательного int, но он вернет false.

1 Ответ

0 голосов
/ 23 мая 2018

У вас есть ошибка на этапе релаксации:

Ваш внешний цикл определяет вершину 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; 
        }
    }
}
...