用C++实现最短路径之Dijkstra算法

1. 前言

最短路径算法是图论中的重要概念,是求解带权图中从一个顶点出发到另一个顶点的最短路径的问题。有许多种算法可以求解最短路径,其中Dijkstra算法是比较常用的一种。

2. Dijkstra算法简介

在有向图或者无向图中,每个边都带有权重,Dijkstra算法可以从一个起点开始找到到图中所有其他顶点的最短路径。

2.1 算法思想

Dijkstra算法采用的是一种贪心的策略,声明一个数组dis来保存源点到各个顶点的最短距离和一个数组path来保存源点到当前顶点的最短路径(点的编号从0开始)。初始时,原点 s 的路径权重被赋为 0 (dis[s] = 0)。若对于顶点 i 有直接的边能到达,即i与s有边,那么将dis[i]的值设为e[s][i],同时将path[i]的值设为s。

接着,我们需要将节点分成两部分:已经求出最短路径的节点集合 P 和未求出最短路径的节点集合 Q。

初始时,集合 P 中只有起点 s;Q 中是除去 P 的所有节点。现在开始一次循环,每次从 Q 中取一个节点 u,作为中介点进行松弛操作。进行松弛操作是指,对于 u 的每一条出边,更新与 u 相邻接的节点(如果在 Q 中)的值。具体更新如下:

如果 dis[u] + e[u][i] < dis[i],则更新dis[i]的值,并将i加入到路径中,更新path[i]=u;

重复这个过程,直到集合 Q 为空。最终dis数组中存储的就是起点到各个顶点的最短路径长度,path数组中存储的是起点到各个顶点的最短路径上的各个顶点。

2.2 算法时间复杂度

Dijkstra算法最坏时间复杂度为O(n^2),但是在稠密图中表现非常优秀。由于其用了小根堆(二叉树)来优化,所以在稀疏图中也可以表现得很优秀。因为堆的加入和删除操作都要花费logN的时间,应该离散的节点非常多才会使算法瓶颈到堆操作上。

3. C++实现

以下是用C++实现Dijkstra算法的代码。

#include

#include

#include

#include

#define MAXN 10005

#define INF 0x3f3f3f3f

using namespace std;

struct Edge {

int v, w;

Edge(int _v, int _w) : v(_v), w(_w) {}

};

vector G[MAXN];

int dis[MAXN];

bool vis[MAXN];

void Dijkstra(int s) {

memset(dis, 0x3f, sizeof(dis));

memset(vis, false, sizeof(vis));

dis[s] = 0;

priority_queue, vector >, greater > > q; // 小根堆

q.push(make_pair(dis[s], s));

while(!q.empty()) {

pair cur = q.top(); q.pop();

int u = cur.second;

if(vis[u]) continue;

vis[u] = true;

for(int i = 0; i < G[u].size(); i++) {

int v = G[u][i].v, w = G[u][i].w;

if(dis[v] > dis[u] + w) {

dis[v] = dis[u] + w;

q.push(make_pair(dis[v], v));

}

}

}

}

int main() {

int n, m, s, t;

scanf("%d %d %d %d", &n, &m, &s, &t);

int u, v, w;

for(int i = 1; i <= m; i++) {

scanf("%d %d %d", &u, &v, &w);

G[u].push_back(Edge(v, w));

G[v].push_back(Edge(u, w)); // 无向图需要添加反向边

}

Dijkstra(s);

printf("%d\n", dis[t]);

return 0;

}

3.1 代码解释

下面对上述代码进行解释。

首先,定义了一个结构体 Edge,表示图的一条边。在vector G[MAXN]中,G[u]存储u节点的所有出边,每条出边记录了终点v以及边权w。

其次,定义了数组dis和vis,分别用于记录源点到各节点的最短距离和该节点是否已经访问过。初始时所有节点的距离均设为INF,表示不可达。

在函数Dijkstra中,我们将初始节点的dis值设为0,并将该节点加入到小根堆中。然后进行while循环,每次从小根堆中取出dis值最小的节点作为中介点进行松弛操作。如果节点u的距离dis[u]已经被确定,就不需要重复访问。

再次思考Dijkstra算法,对于源点s到每一个顶点v,Dijkstra算法只会通过上述while循环松弛所有与s直接相邻的边。由于smaller edge中最小的边被选为u,因此我们只需松弛所有和u直接相邻的边,也仅仅需要O(n)的时间。因此总时间复杂度为O(n^2)。

3.2 算法应用

Dijkstra算法被广泛应用于计算两点间的最短路径,例如路由算法、制定行车路径等。

在图论中,最短路问题是一个基本问题,也是其他问题的基础。因此,深入理解和掌握Dijkstra算法的实现原理和应用场景,具有重要的意义。

4. 结语

本篇文章详细介绍了Dijkstra算法的思想、时间复杂度以及实现过程。尽管Dijkstra算法虽然时间复杂度较高,但是其思想对研究其他最短路径算法起到了很大的指导性作用。因此,在进行最短路径的计算中,要根据实际情况选择合适的算法。

后端开发标签