Я пытался реализовать алгоритм Дейкстры с двоичными кучами для моего класса алгоритмов. Цель состоит в том, чтобы найти длину минимального связующего дерева, найденного через Дейкстру. Я работал с ранее, но с использованием очередей Приоритет. Я обнаружил, что меня запутало управление кучей, и если кто-то мог обнаружить ошибки. Основной метод приведен ниже:
import java.io.File;
import java.util.regex.*;
import java.util.ArrayList;
public class main {
public static void main(String[] args) {
// TODO Auto-generated method stub
try {
File input = new File("filepath\1000.txt");
Scanner scanner = new Scanner(input);
//Regex patterns used to find input size, nodes, and edges
String size = "n=([0-9]*)";
String node = "^[0-9]+";
String edge = "^[\\s]+([0-9]+)[\\s]+([0-9]+)";
Pattern sizePattern = Pattern.compile(size);
Pattern edgePattern = Pattern.compile(edge);
Pattern nodePattern = Pattern.compile(node);
//Loop to fill nodeList
ArrayList <Integer> finalDistances = new ArrayList<>();
MinHeap list = null;
Node currentNode = null;
Edge currentEdge = null;
while(scanner.hasNextLine()) {
String line = scanner.nextLine();
Matcher match1 = sizePattern.matcher(line);
Matcher match2 = nodePattern.matcher(line);
Matcher match3 = edgePattern.matcher(line);
//catches size
if(match1.find()) {
int numberOfNodes = Integer.parseInt(match1.group(1));
//Holds all the nodes to process with Dijkstra's Algo
list = new MinHeap(numberOfNodes);
}
//catches node
if (match2.find()) {
if (!list.contains(Integer.parseInt(line))) {
currentNode = new Node(Integer.parseInt(line));
currentNode.seen = false;
currentNode.distance = Integer.MAX_VALUE;
list.insert(currentNode);
}
else {
currentNode = list.getNode(Integer.parseInt(line));
}
}
//catches edge
if(match3.find()) {
if (!list.contains(Integer.parseInt(match3.group(1)))) {
Node temp = new Node(Integer.parseInt(match3.group(1)));
temp.seen = false;
temp.distance = Integer.MAX_VALUE;
list.insert(temp);
currentEdge = new Edge(Integer.parseInt(match3.group(1)), Integer.parseInt(match3.group(2)));
currentNode.add(currentEdge);
} else {
currentEdge = new Edge(Integer.parseInt(match3.group(1)), Integer.parseInt(match3.group(2)));
currentNode.add(currentEdge);
}
}
}
Node source = list.getNode(0);
source.distance=0;
list.updateNode(source);
int treeLength = 0;
while(!list.isEmpty()) {
currentNode = list.extractMin();
currentNode.seen = true;
ArrayList<Edge> edgeList = currentNode.edges;
for (int i = 0; i < edgeList.size(); i++) {
currentEdge = edgeList.get(i);
if (list.contains(currentEdge.end)) {
int calcDist = currentNode.distance + currentEdge.weight;
if (calcDist < list.getNode(currentEdge.end).distance) {
list.decreaseKey(list.getNode(currentEdge.end), calcDist);
}
}
}
System.out.println(currentNode.toString() + "with distance" +currentNode.distance);
finalDistances.add(currentNode.distance);
}
for (int j = 0; j < finalDistances.size(); j++) treeLength+= finalDistances.get(j);
System.out.println("Tree length is: "+treeLength);
}
//fail safe
catch (Exception ex){
System.out.println("Shit broke!");
}
}
}
Входные данные - это просто форматированный текстовый файл:
0
25 244
108 275
140 273
159 313
219 199
254 392
369 171
518 271
538 250
568 253
603 307
613 196
638 314
1
24 187
43 182
65 331
155 369
182 222
186 426
224 395
233 72
240 128
250 101
269 251
371 73
409 301
444 40
451 262
464 337
517 393
569 171
586 384
599 221
601 145
611 209
616 330
629 324
644 254
646 316
675 237
684 327
695 439
696 288
Первая строка - это количество узлов и ребер. Число на линии само по себе является узлом, а числа после - ребрами с весами. Мой класс Node просто имеет значение int, массив ребер и расстояние от источника. Мой класс Edge имеет значение int и int weight.
import java.util.ArrayList;
public class Node {
int value;
ArrayList<Edge> edges;
boolean seen;
int distance;
public Node(int value) {
edges = new ArrayList<>();
this.value = value;
seen = false;
}
public void add (Edge edge) {
edges.add(edge);
}
@Override
//debugging use
public String toString() {
String listOfEdges= "";
//for (int i = 0; i < edges.size(); i++) {
// listOfEdges = listOfEdges + " ," + Integer.toString(edges.get(i).end);
//}
return "Node: "+Integer.toString(value); //+" Edges: "+listOfEdges;
}
}
public class Edge {
int end;
int weight;
public Edge(int end, int weight) {
this.end = end;
this.weight = weight;
}
@Override
//debugging use
public String toString() {
return "Edge: "+end+" Weight: "+weight;
}
}
Кажется, что после точки, в которой выполняется алгоритм, некоторые вершины остаются бесконечными, а другие - отрицательной бесконечностью. Я использую два массива: первый - это куча, в которой хранятся узлы, а второй - для хранения индексов узлов в куче. Полный класс ниже:
private int capacity;
private int currentSize;
private Node[] heap;
private int[] locations;
//private HashMap<Integer, Integer> locations = new HashMap<>();
public MinHeap(int capacity) {
this.capacity = capacity;
heap = new Node[capacity];
locations = new int[capacity];
//heap[0] = new Node(-1);
//heap[0].distance = Integer.MIN_VALUE;
currentSize = 0;
}
private int getParent(int index) {
return (index-1)/2;
}
private int getLeftChild(int index) {
return index*2+1;
}
private int getRightChild(int index) {
return index*2+2;
}
private void swap(int a, int b) {
Node temp = heap[a];
heap[a] = heap[b];
heap[b] = temp;
//maybe bug
}
Node extractMin() {
Node min = heap[0];
Node last = heap[currentSize-1];
swap (0,currentSize-1);
locations[last.value] = 0;
locations[min.value] = -1;
currentSize--;
heapifyDown(0);
System.out.println("heap size: "+currentSize);
return min;
}
void heapifyDown(int index) {
int currentIndex = index;
int leftIndex = getLeftChild(currentIndex);
int rightIndex = getRightChild(currentIndex);
if (leftIndex < currentSize && heap[currentIndex].distance > heap[leftIndex].distance) {
currentIndex = leftIndex;
}
if (rightIndex < currentSize && heap[currentIndex].distance > heap[rightIndex].distance) {
currentIndex = rightIndex;
}
if (currentIndex != index) {
Node newTop = heap[currentIndex];
Node oldTop = heap[index];
locations[newTop.value] = index;
locations[oldTop.value] = currentIndex;
swap(index,currentIndex);
heapifyDown(currentIndex);
}
}
void heapifyUp(int index) {
int parentIndex = getParent(index);
int currentIndex = index;
Node currentNode = heap[currentIndex];
Node parentNode = heap[parentIndex];
while (currentIndex > 0 && heap[parentIndex].distance > heap[currentIndex].distance) {
System.out.println("Swapped: "+heap[getParent(currentIndex)].toString()+" That has a distance of: "+heap[getParent(currentIndex)].distance+ " With: "+heap[currentIndex]+" Which has a distance of: "+heap[currentIndex].distance);
swap(parentIndex,currentIndex);
locations[currentNode.value] = parentIndex;
locations[parentNode.value] = currentIndex;
currentIndex = parentIndex;
parentIndex = getParent(parentIndex);
System.out.println("min: "+heap[0].toString());
}
}
public void decreaseKey(Node node, int distance) {
int location = locations[node.value];
heap[location].distance = distance;
heapifyUp(location);
}
public void insert(Node node) {
//currentSize++;
int index = currentSize;
heap[currentSize] = node;
locations[node.value] = currentSize;
currentSize++;
heapifyUp(index);
}
public boolean contains(int node) {
return locations[node] != 0 && locations[node] != -1;
}
public boolean isEmpty() {
return currentSize==0;
}
public Node getNode(Node node) {
return heap[locations[node.value]];
}
public Node getNode(int nodeValue) {
return heap[locations[nodeValue]];
}
public void updateNode(Node node) {
heap[locations[node.value]] = node;
}
public void print() {
for (int i = 0; i < currentSize; i++) {
System.out.println(heap[i].toString());
}
}
public Node peek() {
return heap[0];
}
public int size() {
return currentSize;
}
}
Любые отзывы приветствуются.