Djikstra's Shortest path algorithm

Question

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);
        }
    }

You should probably post this on code review rather than stack overflow: codereview.stackexchange.com — John Coleman
– John Coleman, Commented Sep 30, 2016 at 9:49
@JohnColeman They'll have a heart attack! OP: please learn how to format your code properly. This is unreadable. Does it even work properly? It looks like you're using a linked list to keep track of the visited nodes, but how does it reliably choose the shortest hop from the set of visited nodes at each iteration? In any case, a linked list is the wrong data structure for this job. If you use a min-heap, the code will run faster by several orders of magnitude on large data sets. — r3mainer
– r3mainer, Commented Sep 30, 2016 at 9:51
@Tempux Ah, I see it now. And I'm getting a headache. I'm out of here... — r3mainer
– r3mainer, Commented Sep 30, 2016 at 9:56
@squeamishossifrage I was taking at face value OP's claim that it worked but they wanted to know if any edge-case had been missed. If this is the case it seems like a code review problem. Perhaps they are mistaken that the code actually works. — John Coleman
– John Coleman, Commented Sep 30, 2016 at 10:00
@squeamishossifrage to be fair, code being goddamn ugly is not a problem for Code Review, that's what we're here for. The only main requirement is that the OP reasonably believes their code works as intended, and they are actually looking for a general review of their implementation. Asking us to look for edge-cases is borderline. Would be better if OP just said, "My code does this thing, how could it be done better?" — Kaz
– Kaz, Commented Sep 30, 2016 at 10:09

Saeid · Accepted Answer · 2016-09-30 12:18:10Z

3

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.

edited Sep 30, 2016 at 12:18

answered Sep 30, 2016 at 10:41

Saeid

4,2617 gold badges30 silver badges46 bronze badges

Sign up to request clarification or add additional context in comments.

10 Comments

waterbyte Over a year ago

What do u mean by Negative Cycle? As far as i know, Djikstra's Original Implementation don't account for negative weight. And it won't go to cycle because of : if(dist[i]>dist[source]+Ar[source][i]) { dist[i]=Math.min(dist[i],dist[source]+Ar[source][i]); list.add(i); }

waterbyte Over a year ago

Sorry for bad code editing, but I don't have a PC as of now and mobile editing is posing a lot of problem.

waterbyte Over a year ago

I don't see, why there is possibility of Entering a node again because Node is added onto the list only when a shorter path to it is found. And if there would be any Cycle to be formed, then the path to it would be larger and it won't be added to the list.

Saeid Over a year ago

@Waterbyte Dijkstara doesn't give the correct shortest paths when there is negative edges in the graph, but it will terminate. Your code doesn't not terminate when there is a negative cycle. Infinite loop is considered a huge bug.

Saeid Over a year ago

@Waterbyte It is absolutely worse than Dijkstra. Because it is possible that you visit nodes many many times(not twice, just simulate your algorithm on the example graph). Your algorithm complexity is exponential. Dijkstra is linear.

|

S.L. Barth is on codidact.com · Accepted Answer · 2018-01-24 07:54:46Z

1

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.

It will give the correct shortest path even if there is a negative edge (but no negative cycle)
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)

edited Jan 24, 2018 at 7:54

S.L. Barth is on codidact.com

8,25371 gold badges55 silver badges68 bronze badges

answered Jun 7, 2017 at 10:43

Dhruv Singh

2,2732 gold badges13 silver badges20 bronze badges

Collectives™ on Stack Overflow

Djikstra's Shortest path algorithm

2 Answers 2

10 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

10 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related