遍历pair列表的vector出错，Dijkstra算法运行失败排查

Hey there! Let's dig into the issues you're suspecting with your Dijkstra's implementation, plus a few other common pitfalls that might be causing your runtime failures.

You’re right to suspect the vector<list<pair>> adjacency list setup. If you don’t pre-allocate space for the number of vertices, accessing adj[u] (where u is a vertex ID) will either throw an out-of-bounds error or create unintended empty entries behind the scenes—both of which break your algorithm.

For example, if your graph has n vertices, you must initialize the vector with that size first:

// Replace n with your actual number of vertices
vector<list<pair<int, int>>> adj(n);

If your vertices are 1-indexed (instead of 0-indexed), make sure to initialize with n+1 to avoid issues when accessing adj[1] to adj[n]. Without this step, when you try to push edges into adj[u], you’re accessing a position that doesn’t exist, leading to undefined behavior.

Let’s break down possible problems with your range for loop in the shorte... function:

• Empty adjacency list entries: If your adjacency list wasn’t initialized properly, the loop will iterate over empty lists, so no relaxation steps ever run. Your distance array will stay stuck at its initial values (like infinity), making it look like the algorithm failed.
• Incorrect reference usage: For standard relaxation steps, use a const reference to avoid unnecessary copies and ensure you’re reading the correct edge values:

  for (const auto& edge : adj[u]) {
      int neighbor = edge.first;
      int weight = edge.second;
      // Relaxation logic here
  }
  

• Iterating the wrong container: Double-check that you’re iterating over adj[u] (the neighbors of the current vertex u) and not the entire adjacency list by mistake. That’s an easy typo that would completely break the algorithm.

Even if the two issues above are fixed, these easy-to-miss mistakes often cause runtime failures:

• Distance array initialization: Forgetting to set all distances to a large "infinity" value (like INT_MAX or 1e9) and the starting vertex’s distance to 0 will mean your relaxation steps never trigger.
• Priority queue setup: The default priority_queue in C++ is a max-heap, which is the opposite of what Dijkstra’s needs. You must use a min-heap to always extract the vertex with the smallest current distance:

  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> min_heap;
  

• Skipping outdated entries: When you update a vertex’s distance, old entries with larger distances might still be in the priority queue. Always check if the popped distance is greater than the recorded shortest distance for that vertex—if so, skip processing it:

  int current_dist = pq.top().first;
  int u = pq.top().second;
  pq.pop();
  
  if (current_dist > dist[u]) continue; // Skip outdated entry
  

Here’s a minimal, correct implementation you can use to cross-reference your code:

#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <climits>
using namespace std;

void dijkstra(int start, const vector<list<pair<int, int>>>& adj, vector<int>& dist) {
    int n = adj.size();
    dist.assign(n, INT_MAX);
    dist[start] = 0;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        int u = pq.top().second;
        int current_dist = pq.top().first;
        pq.pop();

        if (current_dist > dist[u]) continue;

        for (const auto& edge : adj[u]) {
            int v = edge.first;
            int weight = edge.second;
            if (dist[v] > dist[u] + weight) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }
}

int main() {
    int n = 5; // 0-indexed vertices 0-4
    vector<list<pair<int, int>>> adj(n);
    // Add edges: u -> v with weight w
    adj[0].push_back({1, 2});
    adj[0].push_back({3, 6});
    adj[1].push_back({2, 3});
    adj[1].push_back({4, 5});
    adj[2].push_back({4, 7});

    vector<int> dist;
    dijkstra(0, adj, dist);

    for (int i = 0; i < n; ++i) {
        cout << "Distance from 0 to " << i << ": " << dist[i] << endl;
    }
    return 0;
}

内容的提问来源于stack exchange，提问作者nishant_boro