Source : https://usaco.guide/gold/shortest-paths?lang=cpp#tutorial-1
void dijkstra(int src) { // Source and destination
for (int i = 0; i < N; ++i) dist[i] = LLONG_MAX;
// Set all distances to infinity
using T = pair<ll,int>; priority_queue<T,vector<T>,greater<T>> pq;
dist[src] = 0; // The shortest path from a node to itself is 0
pq.push({0, src});
while (pq.size()) {
ll cdist; int node; tie(cdist, node) = pq.top(); pq.pop();
if (cdist != dist[node]) continue;
for (pair<int, int> i : graph[node]) {
// If we can reach a neighbouring node faster,
// we update its minimum distance
if (cdist+i.second < dist[i.first]) {
pq.push({dist[i.first] = cdist+i.second, i.first});
}
}
}
}
I am not able to understand the explanation given for why removing this line if (cdist != dist[node]) continue;
will lead to a time complexity of O(N^2logN)