Реализация алгоритма Java Prim

Question

Я пытаюсь реализовать алгоритм prim в Java, мой алгоритм, кажется, дает правильные результаты в некоторых случаях, но неверные или частично корректные результаты в других случаях, и я не могу понять, почему, это мой код:

Класс узла

public class Node implements Comparable<Node>{
    private double cost;
    private int dest;
    private int source;
    private Node next;


public Node(double cost, int dest,int source) {
    this.cost = cost;
    this.dest = dest;
    this.source = source;
}
public Node() {

}
public double getCost() {
    return cost;
}
public void setCost(double cost) {
    this.cost = cost;
}
public int getDest() {
    return dest;
}
public void setDest(int dest) {
    this.dest = dest;
}
public Node getNext() {
    return next;
}
public void setNext(Node next) {
    this.next = next;
}



public int getSource() {
    return source;
}
public void setSource(int source) {
    this.source = source;
}
public int compareTo(Node node) {
    if(this.cost> node.getCost())
        return 1;
    else if (this.cost<node.getCost())
        return -1;
    else
        return 0;
}

}

связанный Список класса:

public class LinkedList {
private Node first;
private Node last;
private int counter;

public LinkedList() {

}

public Node getFirst() {
    return first;
}
public Node getLast() {
    return last;
}
public int getCounter() {
    return counter;
}

public Object getFirstNode() {
    if(counter == 0)
        return null;
    else
        return first;

}


public Object getLastNode() {
    if(counter ==0)
        return null;
    else
        return last;
}

public void addLast(double cost,int dest,int source) {
    if (counter == 0) {
        first = last = new Node(cost,dest,source);

    }   
    else {
        Node temp = new Node(cost,dest,source);
        last.setNext(temp);
        last = temp;
    }
    counter++;
}

public void addFirst(double cost,int dest,int source) {
    if (counter == 0) {
        first = last = new Node(cost,dest,source);

    }   
    else {
        Node temp = new Node(cost,dest,source);
        temp.setNext(first);
        first = temp;
    }
    counter++;
}

}

Класс алгоритма Prim:

public class Prim {
    private double[][] t;
    private LinkedList[] list;
    private PriorityQueue heap = new PriorityQueue<Node>();

public Prim(int vertex) {
    t = new double[vertex][3];
    list = new LinkedList[vertex];
    for (int i = 0; i < vertex; i++) {
        list[i] = new LinkedList();
    }
    for (int i = 0; i < vertex; i++) {
        t[i][1] = Integer.MAX_VALUE;
    }
}

public void MST(int start) {
    t[start - 1][0] = 1;
    t[start - 1][1] = 0;
    t[start - 1][2] = 0;

    Node node = list[start - 1].getFirst();
    // vertex-1
    while (node != null) {
        t[node.getDest() - 1][1] = node.getCost();
        t[node.getDest() - 1][2] = node.getSource();
        // vertex - 1
        node = node.getNext();
    }

    // debug
    for (int i = 0; i < t.length; i++) {
        System.out.println('\n');
        for (int j = 0; j < t[i].length; j++) {
            System.out.print(t[i][j] + " ");

        }
    }
    System.out.println('\n');

    while (heap.peek() != null) {
        Node minNode = (Node) heap.poll();
        if (t[minNode.getDest() - 1][0] != 1 && minNode.getCost() <= t[minNode.getDest() - 1][1]) {

            t[minNode.getDest() - 1][0] = 1;

            Node adjacent = list[minNode.getDest() - 1].getFirst();

            while (adjacent != null ) {
                if (t[adjacent.getDest() - 1][0] != 1 && (adjacent.getCost()<t[adjacent.getDest() - 1][1])) {

                    t[adjacent.getDest() - 1][1] = adjacent.getCost();
                    t[adjacent.getDest() - 1][2] = adjacent.getSource();
                }

                adjacent = adjacent.getNext();
            }
        }
    }


}

public void addNode(int index, int cost, int dest) {
    list[index - 1].addLast(cost, dest, index);
    heap.add(new Node(cost, dest, index));
}
public PriorityQueue getHeap() {
    return heap;
}

public void setHeap(PriorityQueue heap) {
    this.heap = heap;
}

public double[][] getT() {
    return t;
}

public void setT(double[][] t) {
    this.t = t;
}

}

В классе драйвера:

Prim prim = new Prim(4);
    prim.addNode(1, 5, 2);
    prim.addNode(1, 4, 4);

    prim.addNode(2, 5, 1);
    prim.addNode(2, 3, 3);
    prim.addNode(2, 2, 4);

    prim.addNode(3, 3, 2);
    prim.addNode(3, 6, 4);

    prim.addNode(4, 4, 1);
    prim.addNode(4, 6, 3);
    prim.addNode(4, 2, 2);
    prim.MST(4);

Создает правильные результаты, если вы печатаете таблицу t с использованием prim.getT () и выполняете итерацию по массиву 2d: (k: известно, d стоимость, p путь или узел, через который я двигаюсь).Обратите внимание, что поскольку граф направлен, необходимо сказать: prim.addNode (1, 5, 2), где 1 - источник, 2 пункт назначения и 5 стоимость, а также: prim.addNode (2, 5, 1), где 2источник, 1 стоимость и 5 место назначения.

kdp

1 0 0

1 2 4

1 3 2

1 4 1

    Prim prim = new Prim(7);
    prim.addNode(1, 2, 2);
    prim.addNode(1, 1, 4);
    prim.addNode(1, 4, 3);

    prim.addNode(2, 2, 1);
    prim.addNode(2, 3, 4);
    prim.addNode(2, 10, 6);

    prim.addNode(3, 4, 1);
    prim.addNode(3, 2, 4);
    prim.addNode(3, 5, 6);

    prim.addNode(4, 1, 1);
    prim.addNode(4, 3, 2);
    prim.addNode(4, 2 ,3);
    prim.addNode(4, 7, 5);
    prim.addNode(4, 8, 6);
    prim.addNode(4, 4, 7);

    prim.addNode(5, 10, 2);
    prim.addNode(5, 7, 4);
    prim.addNode(5, 6, 7);

    prim.addNode(6, 5, 3);
    prim.addNode(6, 8, 4);
    prim.addNode(6, 1, 7);

    prim.addNode(7, 4, 4);
    prim.addNode(7, 6, 5);
    prim.addNode(7, 1, 6);

    prim.MST(4);

Также выдает правильные результаты при печати таблицы:

1 1 4

1 2 1

1 2 4

1 0 0

1 6 7

1 1 7

1 4 4

Однако, если я создаю следующий график:

 Prim prim = new Prim(6);
    prim.addNode(1, 4, 2);
    prim.addNode(1, 5, 6);
    prim.addNode(1, 3, 4);

    prim.addNode(2, 4, 1);
    prim.addNode(2, 3, 3);
    prim.addNode(2, 4, 4);
    prim.addNode(2, 4, 5);

    prim.addNode(3, 3, 2);
    prim.addNode(3, 2, 4);


    prim.addNode(4, 2, 3);
    prim.addNode(4, 4, 2);
    prim.addNode(4, 3 ,1);
    prim.addNode(4, 3, 5);


    prim.addNode(5, 3, 4);
    prim.addNode(5, 4, 2);
    prim.addNode(5, 1, 6);

    prim.addNode(6, 5, 1);
    prim.addNode(6, 1, 5);

     prim.MST(4);

, я получаю следующееРезультаты:

1 3 4

1 3 3

1 2 4

1 0 0

1 1 6

1 2147483647 0

Другими словами, последние две строки неверны, если это поможет, это ссылка на последнюю картинку графиков в Интернете: http://users.monash.edu/~lloyd/tilde/CSC2/CSE2304/Notes/17MST2.shtml

По сути, яЯ храню мои вершины в массиве связанных списков.Первый индекс в массиве содержит связанный список всех узлов, смежных с первой вершиной и так далее.Каждый узел имеет следующие элементы данных:

1 - стоимость, расстояние между источником и назначением;

2 - источник, вершина;

3 - Dest или узел назначения.

Таблица t имеет 3 столбца, первый - это известный узел, второй - стоимость, а третий - путь или номер исходного узла.Начало в основном с какого узла я хочу начать в этом неориентированном графе.Наконец, я хотел бы добавить, что я на самом деле использую этот алгоритм на карте Google, чтобы найти кратчайший прямой путь между двумя точками.Когда я попробовал первые два примера, я подумал, что мой алгоритм был правильным, поэтому я применил его к своей реальной задаче, однако дал неверные результаты, поэтому я выбрал случайный график из Интернета и пропустил его через свой алгоритм, чтобы увидеть, действительно ли он работает, поворотыэто не так.Заранее спасибо, помогите пожалуйста.