java - Android中特定边之间的邻接矩阵中的Dijkstra算法

您好，我在邻接矩阵中找到最短路径时遇到问题。我想找到从startPoint到finishPoint（ex 2-9）的路径。
我的代码在下面，我在“ printPath（parent，parent [j]）;”中有StackOverflowError。线。
我非常谢谢你..

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

最佳答案

我认为您的基本情况有问题。索引j不变，并且函数一次又一次地调用自身，从而导致stackoverflow错误。尝试这个：

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中的for循环，也可以将roomcounter传递给printpath方法来检查j是否大于计数器。