在邻接矩阵中运行 Dijkstra 算法后，线程“main”

Question

我试图在加权邻接矩阵中运行 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);

}

}

}   

Answer 1

这StackOverflowError是由方法中的无限递归触发的path。&nbsp;parents[curr]永远不会保持-1（基本情况），因此递归永远不会停止。您需要确保最终path以 -1 调用curr。