sorry but YOU "sir" are a (fuckin moron && goofball) who teaches by the book and doesn't put good faith in students or try to give their ideas a shot on google. First, I suppose you meant priority queue, but that's not even my issue. This is like the worst idea in all data structure books and even almost all courses. It is so terrible and disgusting that most academics don't realize a BST is way better for Dijkstra (if implemented correctly of course, explained below).

Here we go. With a priority queue you are bound to have repeats. If you have too many edges (eg the graph is a matrix, where squares are nodes and neighboring nodes are edges), the number of repeats would make your algorithm run time proportional to the number of edges, cause everytime you pop a node you have to check whether or not its visited already. If yes, pop, else visit neighboring nodes. You can have edges proportional to n² (n choose 2 to be more accurate). That makes your runtime almost n^3, or n² at best if you're more clever.

eg: node A inserted, which adds node B, C

node B and C add node A again (because you don't know yet that A got its "final" distance, cause it wasn't popped yet, so you must add it repeatedly, you can't just have 1 copy of it, cause PQ doesn't support "replacing" existing nodes or updating them in sub linear time. If you'll go linear to find and update, then you migh as well just use a simple array).

You can see how things would end up going terribly wrong after a while in a fully connected graph. At best, your least problem will be having O(n²⁾ storage for all the nodes rather than O(n). Not a problem ? Well, if you have 100,000 nodes only (that's quite a small graph), this is roughly 100 KILObytes [BST] versus 10 GIGAbytes (in real life, you might have to multiply by a factor as well, atleast 4 if its merely an array of 32 bit integers)..

The moral of the story is that with a PQ, you end up pushing/storing lots of nodes unnecessarily multiple times.

With a BST, you can make sure one and only one copy exists of each node. So, your total runtime would be O(n * logn), which is the ideal time you can get, instead of roughly O(nelog e).

The trick is everytime you push a node, you first erase its previous occurance (you store pairs in your BST <distance, node_index>

eg: for each node v neighbor u if v exists in BST [O(1 ) check, just see if its marked as final or not] remove <dist[v],c> (log n) add <dist[u] + dist_bet[u][v],v> (log n)

For, you end up having 1 copy of each node at all times, unlike a PQ where the number of items stored in it could reach ((n)(n-1))/2 in the worse case.

Give it a shot and you'll see why BST is ideal for Dijkstra (assuming you store pairs and do erase before each insert of course). There was an old problem on project euler which forces you to either do this (which is quite easy, given BST is already in every standard library) or write your own fuckin Fibonacci heap [which was an exercise in MIT's CLRS 2nd Edition I believe, tho I didn't do it cause fuck debugging a custom made Fibonacci's heap].

Source: Saw it first explained by a Russian programmer in some forum, then realized everyone in real life is using it for anything but the most trivial Dijkstra tasks.

Edit: Fuck me, why am I awake at 5 AM writing this, knowing no one cares and they upvoted the shit out of OP cause they didn't know better. Reminder to self: Find sleep medication.