Собственная проблема реализации алгоритма Дейкстры

Question

У меня внутри простого класса Graph эта реализация алгоритма Dijkstra O (n ^ 2), и при отладке его результат отличается от ожидаемого из теста JUnit, и я не могу найти проблему:

    public void Dijkstra(T departureNode) {
    initDijkstra(departureNode);

    ArrayList<GraphNode<T>> V_S = fillWithoutElement(departureNode);

    while (V_S.size() > 0) {
        int w  = chooseMinimum(D);
        nodes.get(w).setVisited(true);
        GraphNode<T> auxW = nodes.get(w);
        V_S.remove(findOnV_S(V_S, auxW));

        for(GraphNode<T> m : V_S) {
            if (D[w] + weights[w][getNode(m.getElement())] < D[getNode(m.getElement())]) {
                D[getNode(m.getElement())] = D[w] + weights[w][getNode(m.getElement())];
                PD[getNode(m.getElement())] = w;
            }
        }
    }
}

Это вспомогательный метод chooseMinimum ():

    private int chooseMinimum(double[] auxD) {
    int res = 0;
    double min = INFINITE;
    for (int i = 0; i < auxD.length; i++) {
        if (!nodes.get(i).isVisited()) {
            if (auxD[i] < min) {
                min = auxD[i];
                res = i;
            }
        }
    }
    return res;
}

И это метод findOnV_S ():

    private int findOnV_S(ArrayList<GraphNode<T>> V_S, GraphNode<T> auxW) {
    int res = 0;
    for(int i = 0; i < V_S.size(); i++) {
        if(V_S.get(i).equals(auxW))
            res = i;
    }
    return res;
}

Это метод initDijkstra ():

public void initDijkstra(T departureNode) {
    if (!itExists(departureNode))
        throw new IllegalArgumentException("Node does not exist");

    D = new double[size];
    PD = new int[size];
    int j = getNode(departureNode);
    // Initialize D
    for (int i = 0; i < size; i++) {
        if (edges[j][i]) {
            D[i] = weights[j][i];
        } else
            D[i] = INFINITE;
    }

    // Initialize PD
    for (int i = 0; i < size; i++) {
        if (edges[j][i])
            PD[i] = getNode(departureNode);
        else
            PD[i] = EMPTY;
    }

    initializeVisitedToFalseExceptStart(departureNode);
}

И это вспомогательный метод initializeVisitedToFalseExceptStart:

    private void initializeVisitedToFalseExceptStart(T departureNode) {
    if (!itExists(departureNode))
        throw new RuntimeException("Invalid node");
    GraphNode<T> element = null;
    for (int i = 0; i < size; i++) {
        element = nodes.get(i);
        if ((element.getElement()).equals(departureNode))
            element.setVisited(true);
        else
            nodes.get(i).setVisited(false);
    }
}

PD: я думаю, что неправильный метод - выбор.getD () вернет двумерный массив, но фактический D в классе Graph является одномерным массивом.

PD3: Это простой тест JUnit:

     try
     {
         g.addNode("V1");
         g.addNode("V2");
         g.addNode("V3");
         g.addNode("V4");
         g.addNode("V5");
         g.addNode("V6");
     }
     catch (Exception e)
     {
         System.out.println ("No repeated nodes are allowed" + e);
     }

     try
     {
         g.addEdge ("V1", "V2", 3.0);
         g.addEdge ("V1", "V3", 4.0);
         g.addEdge ("V1", "V5", 8.0);

         g.addEdge ("V2", "V5", 5.0);

         g.addEdge ("V3", "V5", 3.0);

         g.addEdge ("V5", "V6", 3.0);
         g.addEdge ("V5", "V4", 7.0);

         g.addEdge ("V6", "V4", 2.0);
     }
     catch (Exception e)
     {
         System.out.println ("Starting or arrival node does not exists" + e);
     }

     g.Dijkstra ("V1");
     assertArrayEquals (new double[][]{{Graph.INFINITE, 3.0, 4.0, 12.0, 7.0, 10.0}}, g.getD());
     assertArrayEquals (new int[]{-1, 0, 0, 5, 2, 4}, g.getPD());

Answer 1

Я думаю, что нашел проблему.У вас есть этот метод с именем initializeVisitedToFalseExceptStart (escapeNode) внутри вашего метода initDijkstra.Поэтому, когда первоначальный вызов chooseMinimum выполняется в цикле while, вы находите минимум, не принимая во внимание выслание узла

. Думаю, если вы удалите этот вызов метода внутри метода initDijkstra, ваш алгоритм будет работать нормально.