Priority Queue vs Set

Understanding time complexity of Dijkstra priority queue vs set vs queue-->

Dijkstra's Algorithm using Priority Queue:
vector dijkstra(int V, vector> adj[], int S) {
priority_queue, vector>,
greater>> pq;
vector distTo(V, INT_MAX);
distTo[S] = 0;
pq.push({0, S});
while (!pq.empty()) {
int node = pq.top().second;
int dis = pq.top().first;
pq.pop();
for (auto it : adj[node]) {
int v = it[0];
int w = it[1];
if (dis + w < distTo[v]) {
distTo[v] = dis + w;
pq.push({dis + w, v});
}
}
}
return distTo;
}

Dijkstra's Algorithm using Set:
vector dijkstra(int V, vector> adj[], int S) {
set> st;
vector dist(V, 1e9);
st.insert({0, S});
dist[S] = 0;
while (!st.empty()) {
auto it = *(st.begin());
int node = it.second;
int dis = it.first;
st.erase(it);
for (auto it : adj[node]) {
int adjNode = it[0];
int edgW = it[1];
if (dis + edgW < dist[adjNode]) {
if (dist[adjNode] != 1e9)
st.erase({dist[adjNode], adjNode});
dist[adjNode] = dis + edgW;
st.insert({dist[adjNode], adjNode});
}
}
}
return dist;
}
Comparison:

Data Structure Used:
The first version uses a priority_queue to efficiently extract the minimum distance node.
The second version uses a set to maintain nodes in ascending order based on distances.

Complexity:
The first version (with the priority queue) usually has better time complexity in practice as compared to the second version.
The second version has a higher time complexity due to the overhead of searching and erasing elements from the set.

Code Length:
The first version is generally more concise and easier to read.
The second version involves more lines of code, mainly due to handling set operations.

Efficiency:
The first version is generally more efficient for large graphs due to the efficient extraction of the minimum element from the priority queue.
The second version may be less efficient for large graphs due to the overhead of set operations.

In conclusion, while both versions implement Dijkstra's algorithm, the version using the priority queue is typically more efficient and concise. The version using the set might be useful in certain scenarios or for educational purposes, but for practical implementations, the version with the priority queue is often preferred.