c++ dijkstra算法代码 c++最短路径算法实现-C++-PHP中文网

c++ dijkstra算法代码 c++最短路径算法实现

穿越時空

发布： 2025-12-20 13:50:44

原创

219人浏览过

Dijkstra算法用于求解带权图单源最短路径，适用非负权重边。1. 采用邻接表存储图结构，节省空间；2. 使用优先队列（最小堆）快速选取距离最小节点；3. 通过松弛操作更新邻居距离；4. 利用visited数组避免重复处理；5. 时间复杂度为O((V + E) log V)。示例输出从起点0到各节点的最短距离：节点0:0，节点1:7，节点2:3，节点3:9，节点4:5。

c++ dijkstra算法代码 c++最短路径算法实现

Dijkstra算法是解决带权图单源最短路径问题的经典方法，适用于边权重为非负的图。下面是一个基于邻接表和优先队列（最小堆）实现的C++版本Dijkstra算法，效率较高，时间复杂度为 O((V + E) log V)。

使用优先队列优化的Dijkstra算法实现

该实现使用 STL 中的 priority_queue 和 vector 来表示图和维护待处理节点。

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

// 定义边：目标节点和权重
struct Edge {
    int to, weight;
    Edge(int t, int w) : to(t), weight(w) {}
};

// 定义优先队列中的元素：距离和节点
struct Node {
    int node, dist;
    Node(int n, int d) : node(n), dist(d) {}
    // 重载操作符，使优先队列按距离从小到大排序（最小堆）
    bool operator<(const Node& other) const {
        return dist > other.dist;  // 注意：priority_queue默认是最大堆，所以用>实现最小堆
    }
};

class Graph {
    int V;  // 节点数量
    vector<vector<Edge>> adj;  // 邻接表

public:
    Graph(int v) : V(v) {
        adj.resize(V);
    }

    // 添加边（无向图可调用两次或修改为双向）
    void addEdge(int u, int v, int w) {
        adj[u].push_back(Edge(v, w));
    }

    // Dijkstra算法求最短路径
    void dijkstra(int start) {
        vector<int> dist(V, INT_MAX);  // 距离数组
        vector<bool> visited(V, false); // 访问标记
        priority_queue<Node> pq;

        dist[start] = 0;
        pq.push(Node(start, 0));

        while (!pq.empty()) {
            Node curr = pq.top();
            pq.pop();

            int u = curr.node;
            if (visited[u]) continue;
            visited[u] = true;

            // 遍历所有邻接节点
            for (const Edge& e : adj[u]) {
                int v = e.to;
                int weight = e.weight;

                if (!visited[v] && dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.push(Node(v, dist[v]));
                }
            }
        }

        // 输出结果
        cout << "从起点 " << start << " 到各节点的最短距离：" << endl;
        for (int i = 0; i < V; ++i) {
            if (dist[i] == INT_MAX)
                cout << "到节点 " << i << "：不可达" << endl;
            else
                cout << "到节点 " << i << "： " << dist[i] << endl;
        }
    }
};

登录后复制

主函数示例

创建一个简单图并运行Dijkstra算法：

int main() {
    Graph g(5);  // 创建5个节点的图

    // 添加有向边（起点、终点、权重）
    g.addEdge(0, 1, 10);
    g.addEdge(0, 2, 3);
    g.addEdge(1, 2, 1);
    g.addEdge(1, 3, 2);
    g.addEdge(2, 1, 4);
    g.addEdge(2, 3, 8);
    g.addEdge(2, 4, 2);
    g.addEdge(3, 4, 7);
    g.addEdge(4, 3, 9);

    g.dijkstra(0);  // 从节点0开始计算最短路径

    return 0;
}

登录后复制