CODEWITHSUNDEEP
javaalgorithmgraph-algorithmshortest-pathdijkstra
waterbyte
waterbyte

Reputation: 251

Djikstra's Shortest path algorithm

I am learning Djikstra's and i have prepared the code below based on slightly different idea than Djikstra. Now, In many of the websites, i have seen the use of Extract min and boolean array of visited edges. I have used none and my answer is also correct. Is there any test case or scenario where my algo won't work.

    import java.util.*;
    class ShortestPath2 {
        static int Ar[][];
        static int dist[];

        static int nodes;
        public static void djikstra(int source) {
            LinkedList < Integer > list = new LinkedList < Integer > ();
            dist[source] = 0;

            list.add(source);
            while (!list.isEmpty()) {
                source = list.removeFirst();

                for (int i = 0; i < nodes; i++) {
                    if (Ar[source][i] != 0) {

                        if (dist[i] > dist[source] + Ar[source][i]) {
                            dist[i] = Math.min(dist[i], dist[source] + Ar[source][i]);
                            list.add(i);
                        }
                    }
                }

            }
            System.out.println(Arrays.toString(dist));
        }

        public static void main(String[] args) {
            nodes = 9;

            Ar = new int[nodes][nodes];
            dist = new int[nodes];

            Arrays.fill(dist, Integer.MAX_VALUE);

            Ar = new int[][] {
                 {0,  4, 0,  0,  0,  0, 0,  8, 0},
                 {4,  0, 8,  0,  0,  0, 0, 11, 0},
                 {0,  8, 0,  7,  0,  4, 0,  0, 2},
                 {0,  0, 7,  0,  9, 14, 0,  0, 0},
                 {0,  0, 0,  9,  0, 10, 0,  0, 0},
                 {0,  0, 4, 14, 10,  0, 2,  0, 0},
                 {0,  0, 0,  0,  0,  2, 0,  1, 6},
                 {8, 11, 0,  0,  0,  0, 1,  0, 7},
                 {0,  0, 2,  0,  0,  0, 6,  7, 0}
            };

            djikstra(0);
        }
    }

Upvotes: 0

Views: 848

Answers (2)

Dhruv Singh
Dhruv Singh

Reputation: 2253

Dijkstra's Original Implementation doesn't resolve the negative edge (but can detect it) and negative cycle problem.

To resolve this, we can use the Bellman Ford Algorithm.

  1. It will give the correct shortest path even if there is a negative edge (but no negative cycle)

  2. It can detect whether a negative cycle is there or not (but doesn't give the correct solution if a negative cycle is there, so better we terminate the code)

Upvotes: 1

Saeid
Saeid

Reputation: 4265

The whole idea behind Dijkstra algorithm is using the priority queue. You can't remove the priority queue from Dijkstra and still call it Dijkstra algorithm. What you have written is a BFS without checking for visited. Your code won't terminate if the graph has a negative cycle. Your code will find the shortest path on graph a without negative cycles but the complexity could become exponential. Because there is the possibility of revisiting the nodes over and over again (as a result of removing the visited list). If you add the visited list to your code, your code won't always find the shortest path because you aren't using priority queue. So you need both the priority queue and visited list in order to find the shortest path in linear time.

A --100---B --100-- I---100---O  // A-B, B-I, I-O weight : 100
|        / \       / \        |  // A-C, C-D, ... weight : 1
C-D-E-F-G   H-J-K-L   M-N-P-Q-R

As an example you can use the above graph to see how many times your code will revisit O.

Upvotes: 3

Related Questions