I am trying to do Dijkstra algorithm in java using 25,000 vertices. The program worked when I did 1000 vertices but I am trying it again and it fails.
What I first was make a 2d array to represent the path from each node to each node and what is stored in this double array is the weight.
However out of memory it say java heap space memory ran out at line 39.
This is what the input is like http://pastebin.com/vwR6Wmrh except there now 25,000 vertices and 57604 edges.
The line with a single number is a vertice
the line with two number is which vertice the edge is going to and the weight.
So weight from node 0 to node 25 is 244.
This is my code
import java.io.*; //needed for the file class
import java.util.StringTokenizer;
import java.util.Scanner;
public class ShortestPath {
public static void main(String[] args)
throws IOException {
String filename;
Scanner keyboard = new Scanner(System.in);
System.out.println("HELLO USER, ENTER THE NAME OF THE FILE YOU WANT TO INPUT");
filename = keyboard.nextLine();
FileReader freader = new FileReader(filename);
BufferedReader inputFile = new BufferedReader(freader);
String loco = inputFile.readLine();
System.out.println(loco);
StringTokenizer pedro = new StringTokenizer(loco, "= m n");
int N = Integer.parseInt(pedro.nextToken()); //the number of nodes you have in the array
int inf = 2100000;
int[][] a = new int[N][N]; //this will hold all vertices going to all edges
//int[] d = new int[N]; //distance
//boolean[] kaki = new boolean[N];
//int[] p = new int[N];
//the sum of all the shortest paths
int v = 0; //is for vertices
int x = 0; //is for the edges
int y = 0;
//now we initialize the graph the source node is zero the rest of the paths are inf
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (i != j) {
a[i][j] = inf;
} else {
a[i][j] = 0;
}
}
}
//read the first line
//ok now we are reading the file
//in the file the first line is the vertex
//the second is where it is going and the weight of this edge
//a is the array vertices and edges are stored
while (loco != null) {
loco = inputFile.readLine();
if (loco == null) {
break;
}
StringTokenizer str = new StringTokenizer(loco);
if (str.countTokens() == 1) {
x = Integer.parseInt(str.nextToken());
v = x;
//System.out.println(v);
}
if (str.countTokens() == 2) {
x = Integer.parseInt(str.nextToken());
y = Integer.parseInt(str.nextToken());
//System.out.println( x + " " + y);
a[v][x] = y;
a[x][v] = y; //since the graph goes in multiple directions
}
}
inputFile.close();
System.out.println("-------------");
//here I have constructed the graph yes
//these be examples to make sure its working
//System.out.println(a[0][25]);
//System.out.println(a[0][613]);
//System.out.println(a[613][0]);
//System.out.println(a[899][903]);
//System.out.println(a[991][997]);
inputFile.close();
Dijaskra(0, a, N);
//vertex zero is the shortest path
}
}
