贪心算法最短路径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 算法来提高效率。