在邻接矩阵中运行Dijkstra的算法后,线程“ main”中的异常java.lang.StackOverflowError

库马洛(D.Khumalo):

我试图在加权邻接矩阵中运行Dijkstra算法后打印最短路径。尝试打印出路径时,出现stackoverflow错误。

我已经尝试将开始节点更改为long类型和BigInteger类型,如该平台上先前的答案所建议的那样,我也知道我正在使用递归方法来解决问题。

import java.util.*;

public class djikstra {

private static final int invalid = -1;

public djikstra(int matrix[][],int start) {

    int numVertices = matrix[0].length;
    int [] distances = new int [numVertices];
    boolean [] isAdded = new boolean[numVertices];

    for (int i=0;i<numVertices;i++) {
        distances[i]= Integer.MAX_VALUE;
        isAdded[i] = false;
    }

    distances[(int) start]=0;
    int [] parents = new int [numVertices];
    parents[start] = invalid;

    for(int i=1;i<numVertices;i++) {
        int closestNeighbour = -1;
        int shortDist = Integer.MAX_VALUE;

    for(int j=0; j <numVertices;j++) {
        if(!isAdded[j] && distances[j]<shortDist) {
            closestNeighbour = j;
            shortDist = distances[j];
        }
    }
    isAdded[closestNeighbour]=true;

    for(int j = 0; j <numVertices;j++) {
        int edgeDist = matrix[closestNeighbour][j];
        if(edgeDist > 0 && ((closestNeighbour+edgeDist)<distances[j])) {
            parents[j] = closestNeighbour;
            distances[j] = shortDist + edgeDist;
        }
    }
}
    printSol(start,distances,parents);
 }

private static void printSol(int start,int[] distances,int[] parents) {
    int numVertices=distances.length;
    for(int i=0;i<numVertices;i++) {
        if(i !=start) {
            path(i,parents);
        }
 }
}

private static void path(int curr,int[]parents) {
    if(curr== -1) {
        return;
    }

    path(parents[curr],parents);

}
}

public static void Main(String args[]){
       int matrix2[][]= {{0, 0, 0, 4, 12, 14, 0, 0, 0, 0, 0 ,0, 0, 0}, 
           {0, 0, 0, 0, 0, 0, 0, 12, 0, 8, 0, 18, 15, 7},
           {0, 0, 0, 11, 3, 3, 0, 0, 0, 0, 0, 13, 8, 10}, 
           {4, 0, 0, 0, 10, 12, 0, 0, 0, 0, 10, 10, 13, 0}, 
           {0, 0, 3, 10, 0, 2, 0, 0, 0, 0, 0, 10, 5, 11}, 
           {0, 0, 3, 12, 2, 0, 0, 0, 0, 0, 0, 10, 5, 9 },
           {20, 0, 0, 0, 0, 0, 0, 14, 10, 20, 16, 22, 0, 0}, 
           {0, 12, 0, 0, 0 ,0 ,14, 0, 4, 6, 12, 0,0, 0 },
           {0, 16, 0, 0, 0, 0, 10, 4, 0, 10, 14, 20, 0, 0}, 
           {0, 8, 0, 0, 0, 0, 0, 6, 10, 0, 18, 0, 0, 15 },
           {0, 0, 0, 10, 0, 0, 0, 12, 0, 0, 0, 6, 11, 11}, 
           {0, 0, 0, 10, 10, 10, 0, 0, 0, 0, 6, 0, 5, 11}, 
           {0, 0, 8, 0, 5, 5, 0, 0, 0, 0, 11, 5, 0, 8}, 
           {0, 7, 10, 0, 11, 9, 0, 0, 0, 0, 0, 11, 8, 0}};

    djikstra doDjikstra = new djikstra(matrix2,0);
}   



Expected results:
0 4 13 1
Actual results:
Exception in thread "main" java.lang.StackOverflowError
at helperclasses.djikstra.path(djikstra.java:61)
user7217806:

StackOverflowError通过在一个无限递归触发path方法。parents[curr]从不保持-1(基本情况),因此递归永远不会停止。您将需要确保最终path使用-1进行调用curr

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章

线程main中的java.lang.StackOverflowError

为什么我在递归 java 方法中收到“线程“main”java.lang.StackOverflowError 中的“异常”?

3 Way Quicksort:线程“ main”中的异常java.lang.StackOverflowError

线程“主”中的异常java.lang.StackOverflowError问题

快速排序中的“线程”main“java.lang.StackOverflowError”中的异常,用于大小大于 10000 的排序、反转和相同数据

Python中邻接矩阵的Dijkstra算法

在 main 和用户定义的方法范围之外创建一个对象会给出“线程“main”java.lang.StackOverflowError 中的异常”

这在Java中-线程“主”中的异常java.lang.StackOverflowError

QuickSort在线程“主”中给出异常java.lang.StackOverflowError

空手道0.9.1-线程“主”中的异常java.lang.StackOverflowError

应用程序在Activity中引发java.lang.StackOverflowError异常

当用koin注入UseCase时,方法在android中抛出'java.lang.StackOverflowError'异常

未捕获的异常java.lang.stackoverflowError

由于 DFS 中的迭代器导致的 java.lang.StackOverflowError

testng中的线程“ main”中的异常java.lang.NoClassDefFoundError

java错误:线程“ main”中的异常java.lang.NoClassDefFoundError

错误:java.lang.StackOverflowError

为什么线程“ main”中的异常java.lang.NoClassDefFoundError :?

错误:线程“main”中的异常 java.lang.ArrayIndexOutOfBoundsException

线程“main”中的异常 java.lang.ArrayIndexOutOfBoundsException: 99

线程“main”中的异常 - java.lang.NoClassDefFoundError

线程“main”中的kotlin异常java.lang.IndexOutOfBoundsException

如何修复“线程“main”中的异常java.lang.ExceptionInInitializerError”

线程“main”中的异常 java.lang.IndexOutOfBoundsException:

线程“main”中的 NetBeans 异常 java.lang.NoClassDefFoundError

线程“main”中的错误异常 java.lang.RuntimeException

构造函数中的StackOverflowError异常

java.lang.StackOverflowError引发spark-submit,但不能在IDE中运行

在Java中获取StackOverFlowError