CODEWITHSUNDEEP
javaandroiddijkstrashortest-pathadjacency-matrix
Birgul Ozlem
Birgul Ozlem

Reputation: 51

Dijkstra Algorithm in Adjacency Matrix Between Spesific Edges in Android

Hello i have a problem to find shortest path in adjacency matrix. I want to find path from startPoint to finishPoint(ex 2 - 9). My codes just below and i have StackOverflowError in "printPath(parent, parent[j]);" line. I m so thank you ..

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

Upvotes: 0

Views: 369

Answers (1)

noshusan
noshusan

Reputation: 313

I think you have a problem with your base case. The index j is not changing and the function is calling itself again and again causing stackoverflow error. try this:

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

and you dont need the for loop in printsolution and also you can pass the roomcounter to printpath method to check if j is larger then the counter.

Upvotes: 1

Related Questions