1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Can you provide the test graphs? \$\endgroup\$ – coderodde May 22 at 11:37
  • \$\begingroup\$ String expected = "[0, 3, 2, 4]"; int[][] graph = new int[][]{{0, 5, 2, 0}, {5, 0, 1, 1}, {2, 1, 0, 7}, {0, 1, 7, 0}, }; \$\endgroup\$ – Balkrishan Nagpal May 24 at 2:00
1
\$\begingroup\$

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.

\$\endgroup\$
-1
\$\begingroup\$

Since you maintain all the state in the actual method, this is asking to declare it static. Finally, at the very least, you could isolate popping the open list into its helper auxiliary method. Also, below I provide an alternative implementation with embedded comments whenever I have something to say:

Alternative implementation

import java.util.Arrays;

public class DijkstrasAlgorithm {

    private static int[][] dijkstrasAlgorithm(int[][] graph, int sourceNode) {
        int[] open       = new int[graph.length];
        int[] parents    = new int[graph.length];
        int[] distances  = new int[graph.length];
        boolean[] closed = new boolean[graph.length];

        int openListSize    = 1;
        open[0]             = sourceNode;
        parents[sourceNode] = -1;

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

        distances[sourceNode] = 0;

        while (openListSize != 0) {
            // Pop the open list:
            int minimumPriorityNode = popOpenList(open,
                                                  distances, 
                                                  openListSize);
            openListSize--;
            // Mark the cost distance of minimumPriorityQueue as optimal:
            closed[minimumPriorityNode] = true;

            for (int childNode = 0; childNode < graph.length; childNode++) {
                if (graph[minimumPriorityNode][childNode] == 0
                        || closed[childNode]) {
                    // Once here, there is no directed arc 
                    // (minimumPriorityNode, childNode), or the optimal distance
                    // of childNode is known. Omit it:
                    continue;
                }

                int tentativeCost = distances[minimumPriorityNode] +
                                    graph[minimumPriorityNode][childNode];

                if (distances[childNode] == Integer.MAX_VALUE || 
                    distances[childNode] > tentativeCost) {
                    // Once here, we are encountered childNode the very first 
                    // time, or we are improving its cost:
                    distances[childNode] = tentativeCost;
                    parents[childNode] = minimumPriorityNode;
                    open[openListSize] = childNode;
                    openListSize++;
                }
            }
        }

        return new int[][]{ parents, distances };
    }

    private static final int popOpenList(int[] openList, 
                                         int[] distances,  
                                         int openListSize) {
        int minimumPriority = Integer.MAX_VALUE;
        int minimumPriorityNode = -1; // Must assign some value.
        int minimumPriorityNodeIndex = -1;

        // Find the minimum priority node in the open list:
        for (int i = 0; i < openListSize; i++) {
            int node = openList[i];
            int nodePriority = distances[node];

            if (minimumPriority > nodePriority) {
                minimumPriority = nodePriority;
                minimumPriorityNode = node;
                minimumPriorityNodeIndex = i;
            }
        }

        // Shift all the open list contents on the right of the minimum 
        // priority node to the left:
        for (int i = minimumPriorityNodeIndex; i < openListSize - 1; i++) {
            openList[i] = openList[i + 1];
        }

        return minimumPriorityNode;
    }

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

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {

        //   1   4
        //  / \ / \
        // 0   3   6
        //  \ / \ /
        //   2   5
        int[][] graph = new int[][]{{ 0, 5, 2, 0 },
                                    { 5, 0, 1, 1 },
                                    { 2, 1, 0, 7 },
                                    { 0, 1, 7, 0 }, };

        int[] result = findShortestPathBetween(graph, 0);
        System.out.print("OP result: ");
        System.out.println(Arrays.toString(result));

        int[][] data = dijkstrasAlgorithm(graph, 0);
        System.out.print("Parents:   ");
        System.out.println(Arrays.toString(data[0]));
        System.out.print("Distances: ");
        System.out.println(Arrays.toString(data[1]));
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.