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

可以使用Dijkstra算法或BFS算法求解无向图最短路径。

Dijkstra算法的C++代码实现：

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

const int maxn = 10005; // 图的最大节点数
const int inf = 0x3f3f3f3f; // 表示无穷大

struct Edge {
    int to; // 边的终点
    int cost; // 边的权值
    Edge(int to, int cost) : to(to), cost(cost) {}
};

vector<Edge> G[maxn]; // 存放图的邻接表
int d[maxn]; // 存放最短路径长度
bool used[maxn]; // 标记该节点是否已经确定最短路径

void dijkstra(int s) {
    memset(d, inf, sizeof(d));
    memset(used, false, sizeof(used));
    d[s] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > que;
    que.push(make_pair(0, s));

    while(!que.empty()) {
        pair<int, int> p = que.top();
        que.pop();
        int v = p.second;
        if(used[v]) continue;
        used[v] = true;
        for(int i = 0; i < G[v].size(); i++) {
            Edge e = G[v][i];
            if(d[v] + e.cost < d[e.to]) {
                d[e.to] = d[v] + e.cost;
                que.push(make_pair(d[e.to], e.to));
            }
        }
    }
}

BFS算法的C++代码实现：

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

const int maxn = 10005; // 图的最大节点数
const int inf = 0x3f3f3f3f; // 表示无穷大

struct Edge {
    int to; // 边的终点
    int cost; // 边的权值
    Edge(int to, int cost) : to(to), cost(cost) {}
};

vector<Edge> G[maxn]; // 存放图的邻接表
int d[maxn]; // 存放最短路径长度
bool used[maxn]; // 标记该节点是否已经确定最短路径

void bfs(int s) {
    memset(d, inf, sizeof(d));
    memset(used, false, sizeof(used));
    d[s] = 0;
    queue<int> que;
    que.push(s);

    while(!que.empty()) {
        int v = que.front();
        que.pop();
        used[v] = false;
        for(int i = 0; i < G[v].size(); i++) {
            Edge e = G[v][i];
            if(d[v] + e.cost < d[e.to]) {
                d[e.to] = d[v] + e.cost;
                if(!used[e.to]) {
                    que.push(e.to);
                    used[e.to] = true;
                }
            }
        }
    }
}

其中，G数组存储邻接表，d数组存储最短路径长度，used数组用于标记该节点是否已经确定最短路径。