8

I have read the following but please take a look at my code below.

Why Dijkstra's Algorithm uses heap (priority queue)?

I have two versions of dijkstra, one good version with PQueue, and one bad version with regular linked list queue. 

public static void computeDijkstra(Vertex source) {
    source.minDistance = 0.;
    Queue<Vertex> vertexQueue = new PriorityQueue<Vertex>();
    // Queue<Vertex> vertexQueue = new LinkedList<Vertex>();
    vertexQueue.add(source);

    while (!vertexQueue.isEmpty()) {
        Vertex fromVertex = vertexQueue.poll();

        if (fromVertex.neighbors != null) {
            for (Edge currentEdge : fromVertex.neighbors) {
                Vertex toVertex = currentEdge.target;
                if (currentEdge.weight + fromVertex.minDistance < toVertex.minDistance) {
                    toVertex.minDistance = currentEdge.weight + fromVertex.minDistance;
                    toVertex.previous = fromVertex;
                    vertexQueue.add(toVertex);
                }
            }
        }
    }
}

public static void computeDijkstraBad(Vertex source) {
    source.minDistance = 0.;
    // Queue<Vertex> vertexQueue = new PriorityQueue<Vertex>();
    Queue<Vertex> vertexQueue = new LinkedList<Vertex>();
    vertexQueue.add(source);

    while (!vertexQueue.isEmpty()) {
        Vertex fromVertex = vertexQueue.poll();

        if (fromVertex.neighbors != null) {
            for (Edge currentEdge : fromVertex.neighbors) {
                Vertex toVertex = currentEdge.target;
                if (currentEdge.weight + fromVertex.minDistance < toVertex.minDistance) {
                    toVertex.minDistance = currentEdge.weight + fromVertex.minDistance;
                    toVertex.previous = fromVertex;
                    vertexQueue.add(toVertex);
                }
            }
        }
    }
}

I also have graph creation with a text file like below

0, 1, 2, 3, 4, 5, 6 // vertices
0, 6 // from and to vertex
1, (2-5, 0-4, 4-6) // from vertex 1 it will have edge to 2 with weight 5 ...
0, (4-3, 3-7)
4, (2-11, 3-8)
3, (2-2, 5-5)
2, (6-2, 5-10)
5, (6-3)

Both the implementation renders the following [0, 3, 2, 6] which is the shortest path indeed from 0 to 6!

Now we know, if a Simple BFS is used to find shortest distance with positive integers, there will be cases where it will not find the minimum path. So, can someone give me a counter example for which my Bad implementation will fail to print the right path for a graph. Feel free to give me the answer in the graph format (the sample text file format) that I used.

So far all the graphs I have had, both implementations rendered the right result. This shouldn't happen because the bad implementation is runtime (E+V) and we know we can't find shortest path without at least E log V.

Another example,

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
0, 10
0, (1-9, 2-10, 3-11)
1, (4-1, 5-7)
2, (4-4, 5-3, 6-5)
3, (5-1, 6-4)
4, (7-9, 8-14, 5-3)
5, (7-4, 8-5, 9-9, 6-2)
6, (8-2, 9-2)
7, (10-3)
8, (10-2)
9, (10-5)

Both implementations renders [0, 3, 5, 6, 8, 10], which is the correct shortest path from 0-10.

Community
  • 1
  • 1
Richard Abraham
  • 87
  • 1
  • 4
  • Just come here to say that your bad implementation is O(E logV) too. Actually, the Dijkstra implementation does not improve the worst case, so it does not change the BigO case, but it improves the performance of the commom case – Plínio Pantaleão Apr 28 '16 at 19:50
  • Hi, can you elaborate why the bad one is E log v? It's a simple BFS with a constant time linked list insert and remove. – Richard Abraham Apr 28 '16 at 19:54
  • you have the same loop struct that the good implementation. The only difference is the sequence of your tests. In a better Dijkstra you could stop when you find the first complete solution been sure it is the best solution, that's why it is considered better in the common case. On your codes, both of then have the same running time because they all check all edges (but it is not a need) – Plínio Pantaleão Apr 28 '16 at 20:02
  • Plus, you have a loop on vertex, and for each vertex, a loop on edges. This is definitely not E+V. – Plínio Pantaleão Apr 28 '16 at 20:14

5 Answers5

7

I believe that the algorithm you've given is correct, but that it isn't as efficient as Dijkstra's algorithm.

At a high level, your algorithm works by finding an "active" node (one whose distance has been lowered), then scanning the outgoing edges to activate all adjacent nodes that need their distance updated. Notice that the same node can be made active multiple times - in fact, it's possible that a node will be activated once per time its candidate distance drops, which can happen potentially many times in a run of the algorithm. Additionally, the algorithm you have implemented might put the same node into the queue multiple times if the candidate distance drops multiple times, so it's possible that all dequeues except the first will be unnecessary. Overall, I'd expect this would result in a pretty big runtime hit for large graphs.

In a sense, the algorithm you've implemented is a shortest paths algorithm, but it's not Dijkstra's algorithm. The main difference is that Dijkstra's algorithm uses a priority queue to ensure that every node is dequeued and processed once and exactly once, leading to much higher efficiency.

So I guess the best answer I can give is "your algorithm isn't an implementation of Dijkstra's algorithm, and the reason Dijkstra's algorithm uses a priority queue is to avoid recomputing distances multiple times in the way that your algorithm does."

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • I agree with your assessment. But isn't the runtime still O(E+V) for the bad implementation? Which is better than E LOG(V) as the graph gets bigger and bigger V? That's what bothers me the most. In other words, let's say there are 500 Edges, and 500 Vertices, then the bad one will do E+V = 500+500 = approx. 1000 operations, where as the priority queue will do 500*log(500) = over 4482 operations! – Richard Abraham Apr 28 '16 at 19:48
  • @RichardAbraham I don't think that runtime assessment is accurate. Can you elaborate on how you got a runtime of O(E + V)? (As a note, I have a pretty strong theory background and getting a runtime like that is theoretically impossible, to the best of my knowledge, unless you know something in advance about the edge weights). – templatetypedef Apr 28 '16 at 20:18
5

Your algorithm will find the right result but what your approach is doing is that it kills off the efficiency of Dijkstra's approach.

Example:

Consider 3 nodes named A B C. 

A->C :7 
A->B :2
B->C :3

In your bad approach, You'll first set the shortest path from A to C as 7, and then, as you traverse, you will revise it to 5 (A->B-C)

In Dijkstra's approach, A->C will not be traversed at all because, when using a min-heap, A->B will be traversed first, B will be marked as "traversed", and then B->C will be traversed, and, C will be marked as "traversed". Now, since C is already marked as "traversed", the path A->C (of length 7) will never be checked.

Therefore, as you can see, in your bad approach, you will be reaching C 2 times (A->C & A->B->C), while using Dijkstra's approach, you will go to C only once.

This example should prove that you will have fewer iterations with Dijkstra's algorithm.

attaboy182
  • 2,039
  • 3
  • 22
  • 28
  • I agree totally with this example. But isn't the runtime still O(E+V) for the bad implementation? Which is better than E LOG(V) as the graph gets bigger and bigger V? That's what bothers me the most. – Richard Abraham Apr 28 '16 at 19:38
  • @RichardAbraham No, your implementation is NOT O(V+E). Consider this - what you're doing is . Every edge has two vertices at either end, which means every edge is being traversed twice. – attaboy182 Apr 28 '16 at 20:13
2

Read the others' answers, they are right, and the summary is the bad implement method is correct, but the complexity of the owner's claim(O(E+V)) is not Right. One other thing that no one else has mentioned, and I'll add it here.

This poor implementation also corresponds to an algorithm, which is actually a derivative of BFS, formally known as SPFA. Check out the SPFA algorithm. When the author published this algorithm back in 1994, he claimed it has a better performance than Dijkstra with O(E) complexity, which is Wrong.

It became very popular among ACM students. Due to its simplicity and ease to implement. As for Performance, Dijkstra is preferred.

similar reply ref to this post

Kevin Chou
  • 489
  • 5
  • 8
-1

All of the answers are very well written, so I won't be adding much explanation. I am adding an example that I came across in a comment made by Striver in one of his videos of the graph playlist. Hope it will help to see the issue clearly.

If we don't use Priority Queue while implementing Dijkstra's Algo for an undirected graph with arbitrary edge weights then we might have to visit the same node, again and again, it will not be able to account for arbitrary edge weights.

Take the below example and dry run it by taking a Priority queue and by taking a simple queue, you will see that you have to visit node 6 twice for the normal queue dry run. So, in the case of much larger graphs, this will result in very poor performance.

Edit-- 5 to 6 node edge weight would be 1 and not 10. I will upload the correct image soon.

enter image description here

Arpan Banerjee
  • 826
  • 12
  • 25
-2

when we use the queue the unnecessary reoccurrence of visiting node arises, while in case of priority queue we avoid these things.

Joker38
  • 7
  • 5