Dijkstra-Algorithmus in der Adjazenzmatrix zwischen spezifischen Kanten in Android

Question

Hallo, ich habe ein Problem, den kürzesten Pfad in der Adjazenzmatrix zu finden. Ich möchte den Pfad von StartPoint zu EndPoint (ex 2 - 9) finden. Meine Codes nur unter und ich habe StackOverflowError in "printPath (Eltern, Eltern [j]);" Linie. ich so bin danke ..

public int minDistance(int dist[], boolean sptSet[]) 
{ 
    int min = 999, minIndex = 0; 
    for (int i = 0; i < roomCount; i++) 
    { 
     if (sptSet[i] == false && dist[i] <= min) 
     { 
      min = dist[i]; 
      minIndex = i; 
     } 
    } 
    return minIndex; 
} 

public void printPath(int parent[], int j) 
{ 
    if (parent[j] == -1) 
     return; 

    if (j >= 80) 
     return; 

    printPath(parent, parent[j]); 

    //Log.i("printPath()", "j : " + j); 
    return; 
} 

public void printSolution(int dist[], int n, int parent[]) 
{ 
    int src = 0; 
    //Log.i("printSolution", "Vertex Distance Path"); 
    for (int i = 0; i < roomCount; i++) 
    { 
     //Log.i("printSolution", "src : " + src + " -> i: " + i + " dist[i] : " + dist[i]); 
     printPath(parent, i); 
    } 
} 

public void dijks(int[][] graph, int src) 
{ 
    int[] dist = new int[roomCount]; 
    boolean[] sptSet = new boolean[roomCount]; 
    int[] parent = new int[roomCount]; 

    for (int i = 0; i < roomCount; i++) 
    { 
     parent[0] = -1; 
     dist[i] = 999; 
     sptSet[i] = false; 
    } 

    dist[src] = 0; 

    for (int count = 0; count < roomCount-1; count++) 
    { 
     int u = minDistance(dist, sptSet); 
     sptSet[u] = true; 

     for (int v = 0; v < roomCount; v++) 
     { 
      if (!sptSet[v] && dist[u] + graph[u][v] < dist[v]) 
      { 
       parent[v] = u; 
       dist[v] = dist[u] + graph[u][v]; 
      } 
     } 
     printSolution(dist, roomCount, parent); 
    } 
} 

Answer 1

Ich glaube, Sie ein Problem mit Ihrem Basisfall haben. Der Index j ändert sich nicht und die Funktion ruft sich immer wieder selbst auf und verursacht Stackoverflow-Fehler. versuchen Sie dies:

public void printPath(int parent[], int j) 
{ 
    if (parent[j] == -1) 
     return; 

    if (j >= 80) 
     return; 
    else 
     j++; 

    printPath(parent, parent[j]); 

    //Log.i("printPath()", "j : " + j); 
    return; 
} 

und Sie nicht in printsolution die for-Schleife müssen und auch können Sie die roomcounter zu printpath Methode übergeben zu überprüfen, ob j größer als der Zähler.