无向图最短路径C++实现

下面是无向图最短路径的 C++ 实现，使用 Dijkstra 算法：

const int MAXN = 100005;
const int INF = 0x3f3f3f3f;

struct Edge {
    int to;
    int w;
    int nxt;
} edges[MAXN * 2];

int head[MAXN];
int tot = 0;
int dist[MAXN];

void add_edge(int u, int v, int w) {
    edges[++tot].to = v;
    edges[tot].w = w;
    edges[tot].nxt = head[u];
    head[u] = tot;

    edges[++tot].to = u;
    edges[tot].w = w;
    edges[tot].nxt = head[v];
    head[v] = tot;
}

void dijkstra(int s) {
    memset(dist, -1, sizeof(dist));
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push(make_pair(0, s));
    dist[s] = 0;
    while (!pq.empty()) {
        pair<int, int> p = pq.top();
        pq.pop();
        int u = p.second;
        if (dist[u] < p.first) continue;
        for (int i = head[u]; i; i = edges[i].nxt) {
            int v = edges[i].to;
            int w = edges[i].w;
            if (dist[v] == -1 || dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push(make_pair(dist[v], v));
            }
        }
    }
}

在这个实现中，`add_edge` 函数用于向无向图中加入一条从节点 `u` 到节点 `v` 权重为 `w` 的边。由于是无向图，因此需要同时加入一条从节点 `v` 到节点 `u` 权重为 `w` 的边。

在 `dijkstra` 函数中，每次遍历节点 `u` 的邻接表时，都会遍历 `u` 的所有邻居节点，并计算从源点 `s` 到每个邻居节点的距离。与有向图的实现类似，不同之处在于需要将每条边的两个方向都考虑到，并同时更新两个方向的最短路径。具体地，可以通过在 `add_edge` 函数中加入一条从节点 `v` 到节点 `u` 的边来实现。