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

Question

您好，我在查找邻接矩阵中的最短路径时遇到问题。我想找到从起点到终点的路径(例如 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);
    }
}

Answer 1

我认为您的基本情况有问题。索引 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 是否 比计数器大。