Why does Dijkstra's algorithm need a priority queue when this regular queue version is also correct?

Question

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.

Answer 1

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."