Geek asks and answers

Dijkstra's algorithm using Matrix Issue matrix

'tries to find the shortest path between the first and last node. The problem is that my code always returns 0. I have a feeling because it calculates the distance between the first node and the first node, which goes to zero, but I'm not 100%. Why does my code always return 0?

The adj matrix is ​​[10] [10], and all nodes are connected, and g.network [] [] is the matrix.

private static int dijkstras(Graph g) {
    // Dijkstra Algorithm
    int[] best = new int[g.network.length];
    boolean[] visited = new boolean[g.network.length];
    int max = 10000; // Infinity equivalent.
    for (int i = 0; i < g.network.length; i++)
    {
        best[i] = max;
        visited[i] = false;
    }

    best[0] = 0;

    for(int i = 0; i < g.network.length; i++)
    {
        int min = max;
        int currentNode = 0;
        for (int j = 0; j < g.network.length; j++)
        {
            if (!visited[j] && best[j] < min)
            {
                currentNode = j;
                min = best[j];
            }
        }
        visited[currentNode] = true;
        for (int j = 0; j < g.network.length; j++)
        {
            if (g.network[currentNode][j] < max && best[currentNode] + g.network[currentNode][j] < best[j])
            {
                best[j] = best[currentNode] + g.network[currentNode][j];
            }
        }
    }
            return best[g.network.length - 2];
}
+3
source share
2 answers

I think that maybe I solved the problem by changing the code as follows (now I go to the starting point instead of hardcoded to "0"):

    private static int dijkstras(Graph g, int start) // Added a start point.
    {
    // Dijkstra Algorithm
    int[] best = new int[g.network.length];
    boolean[] visited = new boolean[g.network.length];
    int max = 10000; // Infinity equivalent.
    for (int i = 0; i < g.network.length; i++)
    {
        best[i] = max;
        visited[i] = false;
    }

    best[start] = start; // Changed the 0 to variable start.

    for(int i = 0; i < g.network.length; i++)
    {
        int min = max;
        int currentNode = 0;
        for (int j = 0; j < g.network.length; j++)
        {
            if (!visited[j] && best[j] < min)
            {
                currentNode = j;
                min = best[j];
            }
        }
        visited[currentNode] = true;
        for (int j = 0; j < g.network.length; j++)
        {
            if (g.network[currentNode][j] < max && best[currentNode] +   g.network[currentNode][j] < best[j])
            {
                best[j] = best[currentNode] + g.network[currentNode][j];
            }
        }
    }
            return best[g.network.length - 2];
}

I ran this code through a for and voila loop .... now only zero is not returned.

+2
source

, , dijkstra, , node node.

+1

More articles:


All Articles