c++实现BFS求最短路径.
时间: 2023-08-30 17:07:05 浏览: 51
好的,以下是一个基于C++的BFS求最短路径的示例代码:
```cpp
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int MAXN = 1005; // 最大节点数
const int INF = 0x3f3f3f3f; // 无穷大
int n, m; // n表示节点个数,m表示边数
int dis[MAXN]; // 存储起点到每个节点的距离
bool vis[MAXN]; // 记录每个节点是否被访问过
int head[MAXN], to[MAXN<<1], nxt[MAXN<<1], edge[MAXN<<1], cnt; // 邻接表存图
void addEdge(int u, int v, int w) {
to[++cnt] = v;
nxt[cnt] = head[u];
edge[cnt] = w;
head[u] = cnt;
}
void bfs(int start) {
memset(dis, INF, sizeof(dis)); // 初始化距离为无穷大
memset(vis, false, sizeof(vis)); // 初始化所有节点都未被访问过
dis[start] = 0; // 起点到自己的距离为0
vis[start] = true; // 起点已经访问过了
queue<int> q; // 定义一个队列,用于广度优先搜索
q.push(start); // 将起点加入队列
while (!q.empty()) {
int u = q.front();
q.pop(); // 取出队首节点
for (int i = head[u]; i; i = nxt[i]) {
int v = to[i], w = edge[i];
if (!vis[v]) { // 如果这个节点未被访问过
dis[v] = dis[u] + w; // 更新距离
vis[v] = true; // 标记为已访问
q.push(v); // 将其加入队列
}
}
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int u, v, w;
cin >> u >> v >> w;
addEdge(u, v, w);
addEdge(v, u, w); // 无向图需要加两条边
}
int start;
cin >> start;
bfs(start);
for (int i = 1; i <= n; ++i) {
if (dis[i] != INF) {
cout << start << " 到 " << i << " 的最短距离为:" << dis[i] << endl;
}
}
return 0;
}
```
这段代码使用邻接表存图,时间复杂度为O(n+m),其中n表示节点数,m表示边数。在实际使用中,可以根据自己的需求进行修改。