AndroidのSpesific Edge間の近接行列におけるDijkstraアルゴリズム

Question

こんにちは私は隣接行列で最短経路を見つけるのに問題があります。私はstartPointからfinishPointまでのパスを見つけたいと考えています（例2 - 9）。 「printPath（parent、parent [j]）;」にStackOverflowErrorがあります。ライン。 私はmが、私は、あなたの基本ケースに問題があると思う

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

..あなたに感謝します。インデックスjは変更されておらず、この関数はスタックオーバーフローエラーを繰り返し発生しています。この方法を試してください。

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

、あなたはprintsolutionでループのための必要ないけないし、また、あなたがjはカウンター、その後も大きいかどうかを確認するためにroomcounter方法printpathに渡すことができます。