无向图最短路径C++实现
时间: 2023-10-20 13:33:33 浏览: 46
以下是无向图最短路径的C++实现,使用了Dijkstra算法:
```c++
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int INF = 1e9; // 定义一个大数表示无穷
// 无向图最短路径实现
void dijkstra(vector<vector<int>>& graph, int start, vector<int>& dist) {
int n = graph.size();
dist.resize(n, INF); // 初始化距离为无穷大
dist[start] = 0; // 起点到自己的距离为0
// 定义优先队列,按距离从小到大排序
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
q.push({0, start});
while (!q.empty()) {
int d = q.top().first;
int u = q.top().second;
q.pop();
// 如果距离已经大于等于当前最短距离,则不需要再考虑以该点为起点的路径
if (d > dist[u]) continue;
// 遍历该点的所有邻居
for (int i = 0; i < n; i++) {
if (graph[u][i] == 0) continue; // 如果两点之间没有边,则跳过
int v = i;
int w = graph[u][v];
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
q.push({dist[v], v});
}
}
}
}
int main() {
// 定义无向图
vector<vector<int>> graph = {
{0, 1, 5, 0, 0, 0},
{1, 0, 2, 7, 4, 0},
{5, 2, 0, 0, 0, 3},
{0, 7, 0, 0, 1, 2},
{0, 4, 0, 1, 0, 6},
{0, 0, 3, 2, 6, 0}
};
int start = 0; // 起点为0
vector<int> dist; // 定义存储最短距离的数组
dijkstra(graph, start, dist); // 调用Dijkstra算法
// 输出各点到起点的最短距离
for (int i = 0; i < dist.size(); i++) {
cout << "从" << start << "到" << i << "的最短距离为:" << dist[i] << endl;
}
return 0;
}
```