C++实现Dijkstra算法

C++实现Dijkstra算法攻略

算法简介

Dijkstra算法是一个在加权图中查找单源最短路径的贪心算法。在开始时，所有节点被分为两个集合：已知最短路径的节点和未知最短路径的节点。对于未知最短路径的节点，算法通过已知最短路径的节点来更新这些节点到源点的距离，最终得到源点到图中所有节点的最短路径。

算法步骤

1. 初始化图中所有节点的距离为无穷大，除源点的距离为0；
2. 将所有节点加入未知节点集合；
3. 从未知节点集合中选择一个最近的节点（即到源点距离最小）；
4. 更新该节点的所有邻居节点的距离，如果距离更短，则修改距离；
5. 重复步骤3-4，直到所有节点均被加入已知节点集合。

C++实现示例：

以下是一个简单的使用邻接矩阵实现Dijkstra算法的示例，其中图的大小为5 * 5。我们以节点2作为源节点。

#include<bits/stdc++.h>
using namespace std;

const int N = 105;
const int INF = 999999;
int n, m;
int graph[N][N];  //邻接矩阵
int d[N];         //存储节点到源点的最短距离
bool vis[N];      //记录节点是否在已知节点集合中

//Dijkstra算法函数
void Dijkstra(int src) {
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= n; i++) d[i] = graph[src][i];
    vis[src] = true;
    for (int i = 1; i < n; i++) {  //遍历除源点外的所有节点
        int u = -1, mn = INF;
        for (int j = 1; j <= n; j++) {
            if (!vis[j] && d[j] < mn) {
                u = j;
                mn = d[j];
            }
        }
        if (u == -1) return;  //无法到达目标点
        vis[u] = true;
        for (int j = 1; j <= n; j++) {
            if (!vis[j] && graph[u][j] != INF) {
                d[j] = min(d[j], d[u] + graph[u][j]);
            }
        }
    }
}

int main() {
    cin >> n >> m;
    memset(graph, INF, sizeof(graph));
    for (int i = 1; i <= n; i++) graph[i][i] = 0;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u][v] = min(graph[u][v], w);  
        graph[v][u] = min(graph[v][u], w);  //无向图需要加上反向边
    }
    int src = 2;  //源点为2
    Dijkstra(src);
    for (int i = 1; i <= n; i++) {
        cout << d[i] << " ";
    }
    cout << endl;
    return 0;
}

第二个示例是使用邻接表实现Dijkstra算法，相比邻接矩阵每次更新节点的距离时速度更快。相同的，我们以节点2作为源节点。

#include<bits/stdc++.h>
using namespace std;

const int N = 105;
const int INF = 999999;
int n, m;
struct Edge{   //邻接表中的边
    int to, w;
    Edge(int u, int v):to(u),w(v){}
    bool operator < (const Edge &e) const {
        return w > e.w;
    }
};
vector<Edge> graph[N];  //邻接表
int d[N];               //存储节点到源点的最短距离
bool vis[N];            //记录节点是否在已知节点集合中

//Dijkstra算法函数
void Dijkstra(int src) {
    memset(vis, 0, sizeof(vis));
    memset(d, INF, sizeof(d));
    priority_queue<Edge> q;  //使用优先队列，堆优化
    q.push(Edge(src, 0));
    d[src] = 0;
    while(!q.empty()) {
        Edge u = q.top();
        q.pop();
        if(vis[u.to]) continue;
        vis[u.to] = true;
        for(int i = 0; i < graph[u.to].size(); i++) {
            Edge v = graph[u.to][i];
            if(vis[v.to]) continue;
            if(d[v.to] > d[u.to] + v.w) {  //松弛操作，更新距离
                d[v.to] = d[u.to] + v.w;
                q.push(Edge(v.to, d[v.to]));
            }
        }
    }
}

int main() {
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back(Edge(v, w));
        graph[v].push_back(Edge(u, w));  //无向图需要加上反向边
    }
    int src = 2;  //源点为2
    Dijkstra(src);
    for(int i = 1; i <= n; i++) {
        cout << d[i] << " ";
    }
    cout << endl;
    return 0;
}

以上两个示例均可在O(n^2)的时间内求解单源最短路径。