Implementation of Dijkstra algorithm

Question

I am trying to implement Dijkstra algorithm. I try to calculate cost of reaching every node from first node. Though I have tried with couple of graphs and results are correct but I have one doubt which leads me to think that something is wrong with my implementation. Here is my implementation

private int[] findShortestPathBetween(int[][] graph, int src) {

    int[] result = new int[graph.length];
    for (int i = 0 ; i < result.length ; i++) {
        result[i] = Integer.MAX_VALUE;
    }

    result[src] = 0;

    boolean[] visited = new boolean[graph.length];

    int i = 0;
   while (true) {
        for (int kk = 0 ; kk < graph.length ; kk++) {
            if (graph[i][kk] != 0 ) { // edge between nodes exists
                int previousCost = result[i];
                if (previousCost == Integer.MAX_VALUE) {
                    previousCost = 0;
                }
                int newCost = previousCost + graph[i][kk];
                newCost = Math.min(newCost, result[kk]);
                if (newCost != result[kk]) {
                    visited[kk] = false; //weight of visited node changed, remove it from visited nodes.
                }
                result[kk] = newCost;
            }
        }
        visited[i] = true;

        int nextNode = -1;
        int nextNodeCost = Integer.MAX_VALUE;

        for (int k = 0 ; k < graph.length ; k++) {
            if (!visited[k]) {
                nextNode = k;
                break;
            }
        }

        if (nextNode == -1) {
            break;
        }

        i = nextNode;
   }
    return result;
}

I think line containing following code should not be required.

visited[kk] = false;

Here I am marking an already visited node as not visited if its cost has changed. Not doing this gives wrong results. As per my understanding this should not be required because if a node has been marked visited it should never be visited again.

I am trying to implement Dijkstra without using any queue (using queue is 2nd part of my implementation).

Please check and confirm whether my implementation has any gaps or this is expected when we are not using queue to implement Dijkstra algorithm.

Assumptions: I have used 2D array to represent my graph. If edge exist between 2 nodes corresponding entry in array is non-zero and if edge does not exist corresponding entry contains 0.

Answer 1

The graph is actually an adjacency graph. This is a much better name than graph to avoid people confusing it with a grid of nodes.

The next node should be the unvisited node with the lowest cost.

for (int k = 0 ; k < graph.length ; k++) {
    if (!visited[k] && result[k] < nextNodeCost) {
        nextNode = k;
        nextNodeCost = result[k];
    }
}

This way you avoid needing to visit nodes multiple times because you will then never change a visited node's cost.

The result array should be initialized with result[0] = 0; then you can remove the check in the for loop.