广度优先解决最短路径问题的C++代码参考

在C++中，使用广度优先搜索（BFS）算法来解决最短路径问题可以借助队列的数据结构，特别是在无权图（所有边权重都为1）或者需要找到最短路径的情况下非常合适。这里提供一个基本的Dijkstra算法的简化版，因为Dijkstra适用于有向图或加权图：

#include <iostream>
#include <queue>
#include <vector>
#include <limits>

using namespace std;

// 定义邻接表存储图
struct Edge {
    int to, weight;
};

class Graph {
private:
    vector<vector<Edge>> adj; // 用于存储邻接列表

public:
    void addEdge(int src, int dest, int weight = 1) {
        adj[src].push_back({dest, weight});
        adj[dest].push_back({src, weight}); // 如果图是非加权的，这里加上weight=1
    }

    pair<int, vector<int>> bfs(int start) {
        vector<int> dist(adj.size(), INT_MAX); // 初始化距离数组
        dist[start] = 0; // 设置起点距离为0
        queue<int> q; // 创建一个队列
        q.push(start);

        while (!q.empty()) {
            int curr = q.front(); // 取出队首元素
            q.pop();

            for (const Edge& edge : adj[curr]) { // 遍历邻居
                int nextDist = dist[curr] + edge.weight;
                if (nextDist < dist[edge.to]) { // 更新目标节点距离
                    dist[edge.to] = nextDist;
                    q.push(edge.to);
                }
            }
        }

        return make_pair(dist.back(), dist);
    }
};

int main() {
    Graph g;
    g.addEdge(0, 1, 1); // 示例添加一条边
    g.addEdge(1, 2, 1);
    g.addEdge(2, 3, 1);
    g.addEdge(3, 4, 1);
    g.addEdge(4, 0, 1);

    auto result = g.bfs(0); // 从节点0开始搜索
    cout << "Shortest path from node 0 is: " << result.first << endl;
    cout << "Path: ";
    for (int i : result.second)
        cout << i << " -> ";

    return 0;
}

这段代码首先定义了一个邻接列表表示图，然后实现了BFS算法，最后在`main()`函数中演示了如何找出从节点0到其他节点的最短路径。