Dijkstra算法在java运行出堆space？

Question

我正在尝试使用 25,000 个顶点在 java 中执行 Dijkstra 算法。该程序在我执行 1000 个顶点时有效，但我再次尝试但失败了。

我首先做一个二维数组来表示从每个节点到每个节点的路径，这个双数组中存储的是权重。

但是内存不足它说 java 堆 space 内存运行在第 39 行。

这就是输入的样子 http://pastebin.com/vwR6Wmrh 除了现在有 25,000 个顶点和 57604 条边。

只有一个数字的线是一个顶点

有两个数字的线是边缘将要到达的顶点和权重。

所以节点0到节点25的权重是244.

这是我的代码

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

Answer 1

基于邻接矩阵的图形表示占用大量内存（如此处所述wiki）。你能试试图的邻接表表示吗？如果你有足够的 RAM 容量，矩阵表示也应该有效。您可以尝试增加启动 VM 参数。

Answer 2

您正在使用邻接矩阵来存储边。该矩阵甚至包含不存在边的条目。

如果您有 25.000 个顶点，则邻接矩阵有 25.000^2 = 625.000.000 个条目。假设 Java 非常有效地存储这些，这至少需要 2.500.000.000，即 Java 堆 space 的 ~ 2.32 GibiBytes。

您可以尝试运行您的 JVM java -Xmx3g 以提供更大的堆大小。当然，这只适用于 64 位 Java。

然而，真正的解决方案是使用仅 0.00018)

的 more space efficient implementation for edge representation since your graph is clearly sparse (i.e. has a density

Dijkstra算法在java运行出堆space？

The Dijkstra algorithm in java running out heap space?

java

graph-algorithm