Dijkstra's Algorithm using Adjacency Matrix Issue

Question

'm trying to retrieve the shortest path between first and last node. The problem is my code always returns 0. I have a feeling this is because it's computing the distance between first node and first node, which is going to zero, but i'm not 100%. Why is my code always returning 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's 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];
}

Solution 1

I think I may have solved the issue, by modifying the code as follows (I'm now passing in a start point instead of the hard-coded in "0"):

    private static int dijkstras(Graph g, int start) // Added a start point.
    {
    // Dijkstra's 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 loop and voila....not just zero's being returned now.

Solution 2

I read your code and I'm almost sure it's correct dijkstra algorithm so I think maybe you have a zero path between your first node and last node.

Comments

[JasonMortonNZ]

I can't answer my own question because of a to low rep, but I have pasted my fix here. You were right, because I set best[0] = 0 it was always returning zero as it was a zero path between nodes. pastebin.com/nmp8P1zW