Inconsistent Results from Dijkstra's Algorithm in C++ - Priority Queue Issues
I'm trying to configure I'm relatively new to this, so bear with me. I'm working on a personal project and I'm implementing Dijkstra's algorithm in C++ to find the shortest paths in a weighted graph, but I'm getting inconsistent results. The algorithm works fine for small graphs, but when I increase the number of nodes and edges, it sometimes returns incorrect distances. Here's a simplified version of my implementation: ```cpp #include <iostream> #include <vector> #include <queue> #include <limits> using namespace std; typedef pair<int, int> pii; // {distance, vertex} vector<int> dijkstra(int start, int n, const vector<vector<pii>>& graph) { vector<int> distances(n, numeric_limits<int>::max()); priority_queue<pii, vector<pii>, greater<pii>> pq; distances[start] = 0; pq.push({0, start}); while (!pq.empty()) { int currDist = pq.top().first; int u = pq.top().second; pq.pop(); if (currDist > distances[u]) continue; // Skip stale entries for (const auto& edge : graph[u]) { int v = edge.first; int weight = edge.second; if (currDist + weight < distances[v]) { distances[v] = currDist + weight; pq.push({distances[v], v}); } } } return distances; } ``` When I run this with a graph that has about 1000 nodes and 5000 edges, I sometimes find that the distances to certain nodes aren't the shortest ones. For example, the distances to node 123 can show as `INF` while I know there's a path to it. I checked for negative weights and confirmed there are none, and I'm using `std::numeric_limits<int>::max()` for initial distance values. I tried adding debug prints to see the contents of the priority queue and the distance array after each iteration, but everything looks correct at a glance. Could this be an scenario with how I'm handling the priority queue? I suspect there might be a question with stale entries being pushed into the queue, but I'm not entirely sure how to fix it. I'm using C++17 and compiling with g++ 9.3.0. Any insights into why Dijkstra's might be failing in this case would be greatly appreciated. I'm working on a application that needs to handle this. Thanks in advance! Thanks, I really appreciate it! I appreciate any insights!