正文

掌握Dijkstra算法，C++实战攻略：从原理到代码实现，一招解决最短路径问题

/0 浏览量
0530

Dijkstra算法是一种经典的图论算法，用于在加权图中找到从一个顶点到其他所有顶点的最短路径。它特别适用于没有负权边的图。本文将带您深入了解Dijkstra算法的原理，并通过C++实战，一步步实现这个算法，帮助您更好地理解和应用它。

Dijkstra算法原理

1. 算法概述

Dijkstra算法的基本思想是使用一个优先队列（通常是一个最小堆）来维护当前已探索顶点的距离。算法从源点开始，逐步探索其他顶点，并更新它们到源点的最短距离。

2. 算法步骤

  1. 初始化所有顶点的距离为无穷大，除了源点，其距离为0。
  2. 将所有顶点加入优先队列。
  3. 当优先队列为空时，重复以下步骤：
    • 从优先队列中取出距离最小的顶点u。
    • 对于u的每个相邻顶点v，如果从源点到v的路径通过u更短，则更新v的距离。
    • 将更新后的v加入优先队列。
  4. 当算法完成时，所有顶点的距离都将是它们到源点的最短距离。

C++实战

1. 数据结构

为了实现Dijkstra算法，我们需要定义一些数据结构来存储图的信息和算法状态。

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

using namespace std;

// 图的邻接表表示
struct Edge {
    int to;
    int weight;
};

vector<vector<Edge>> adjList;

// 优先队列，用于存储顶点和它们的距离
struct Pair {
    int node;
    int dist;
    Pair(int n, int d) : node(n), dist(d) {}
    bool operator>(const Pair& p) const {
        return dist > p.dist;
    }
};

priority_queue<Pair, vector<Pair>, greater<Pair>> pq;

2. Dijkstra算法实现

void dijkstra(int src) {
    int n = adjList.size();
    vector<int> dist(n, INT_MAX);
    dist[src] = 0;
    pq.push(Pair(src, 0));

    while (!pq.empty()) {
        Pair u = pq.top();
        pq.pop();

        for (Edge& edge : adjList[u.node]) {
            int v = edge.to;
            int weight = edge.weight;

            if (dist[u.node] + weight < dist[v]) {
                dist[v] = dist[u.node] + weight;
                pq.push(Pair(v, dist[v]));
            }
        }
    }

    // 打印最短路径距离
    for (int i = 0; i < n; ++i) {
        cout << "Distance from " << src << " to " << i << " is " << dist[i] << endl;
    }
}

3. 主函数

int main() {
    // 构建图
    int n, m;
    cin >> n >> m;
    adjList.resize(n);
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adjList[u].push_back({v, w});
        adjList[v].push_back({u, w}); // 无向图
    }

    // 执行Dijkstra算法
    int src;
    cin >> src;
    dijkstra(src);

    return 0;
}

总结

通过本文的介绍，您应该已经对Dijkstra算法有了深入的理解。通过C++实战，您不仅能够掌握算法的实现，还能够将其应用到实际问题中。希望这篇文章能够帮助您在算法学习的道路上更进一步。

-- 展开阅读全文 --