贪心算法最短路径c++代码
时间: 2023-10-02 13:04:39 浏览: 84
以下是使用贪心算法求解最短路径的C++代码示例:
```c++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int INF = 1e9;
int main() {
int n, m;
cin >> n >> m; // n 为节点数,m 为边数
vector<vector<pair<int, int>>> adj(n); // 邻接表表示图
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w; // 输入起点、终点和边权
adj[u].push_back({v, w}); // 存储邻接节点和边权
adj[v].push_back({u, w});
}
vector<int> dist(n, INF); // 到每个节点的距离初始化为无穷大
vector<bool> vis(n, false); // 是否已访问该节点
dist[0] = 0; // 起点到自身的距离为 0
for (int i = 0; i < n; i++) {
int u = -1; // u 表示当前最近的未访问节点
for (int j = 0; j < n; j++) {
if (!vis[j] && (u == -1 || dist[j] < dist[u])) {
u = j;
}
}
vis[u] = true; // 标记该节点已访问
for (auto& [v, w] : adj[u]) { // 遍历 u 的所有邻接节点 v
if (!vis[v]) {
dist[v] = min(dist[v], dist[u] + w); // 更新到 v 的最短距离
}
}
}
for (int i = 0; i < n; i++) {
cout << "Node " << i << ": " << dist[i] << endl;
}
return 0;
}
```
该算法的时间复杂度为 $O(n^2)$,其中 $n$ 为节点数。在稠密图中,该算法表现良好,但在稀疏图中,可以使用堆优化的 Dijkstra 算法来提高效率。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)