我試圖在加權鄰接矩陣中運行 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);}}}
1 回答

瀟瀟雨雨
TA貢獻1833條經驗 獲得超4個贊
這StackOverflowError
是由方法中的無限遞歸觸發的path
。 parents[curr]
永遠不會保持-1(基本情況),因此遞歸永遠不會停止。您需要確保最終path
以 -1 調用curr
。
添加回答
舉報
0/150
提交
取消