Dijkstra学习笔记

介绍

这个算法适用于非负权图中求单源最短路(一个顶点到其他所有顶点的最短路),有着稳定优秀的时间复杂度,暴力Dij时间复杂度为O(n2)O(n^2),堆优后为O(mlogn)O(mlogn)。事实上mmn2n^2是同阶的,不过一般情况下mm远小于n2n^2,这种图被称为稀疏图;而mm相对较大的图则被称为稠密图,这种情况下暴力Dij可能要比堆优Dij更优。

该算法主要思想是将所有结点分为两个集合:已确定最短路径长度d[x]\rm d[x]的与没确定的。最开始前面的集合中只有起点ss。然后将前一个集合中的所有出边进行松弛,在后面的集合中选出最短路d[x]\rm d[x]最小的结点并标记访问,加入前面的集合中。直到所有节点都访问过即后一个集合没有元素,算法结束。

可以通过反向建图(将每条有向边的起点与终点互换)来求所有点到达一个固定点的最短路,只需要反向建图之后以到达的点为起点进行Dij。

实现

存图

这里使用邻接表进行存图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const int MAXN = 100000 + 5;
const int MAXM = 200000 + 5;

struct Edge { //用来存每条边的终点,下一条边的边号,权值
int e, next, d;
}ed[MAXM];

int first[MAXN], en; //first数组为以 i 为起点的第一条边的边号

void add_edge(int s, int e, int d) { //单向边加边
en++;
ed[en].next = first[s];//第en条边的下一条边更改为以s为起点的第一条边
first[s] = en; //将以s为起点的第一条边改为en
ed[en].e = e; //终点
ed[en].d = d; //边权
}

Dijkstra

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int d[MAXN];     //保存从起点s到i的最短路径长度
bool vis[MAXN]; //布尔类型数组用来记录结点i是否被访问
priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > q;
//含有两个元素的大根堆。由于默认先比较前一项,所以前一项为权值,后一项为结点编号
inline void Dijkstra(int s) { //s为起点编号
memset(d,0x3f,sizeof(d)); //0x3f3f3f3f可视为无限大,可以相加也可以使用memset进行填充
d[s] = 0; //将起点到起点的距离初始化为0
q.push(mark_pair(0, s)); //将结点s存入堆中
while(!q.empty()) {
int now = q.top().second; q.pop(); //取出优先队列中的第一个点
if(!vis[now]) {
vis[now] = true;
for(int i = first[now]; i; i = ed[i].next) { //枚举出边
int e = ed[i].e;
if(d[e] > d[now] + ed[i].d) { //松弛
d[e] = d[now] + ed[i].d;
q.push(make_pair(d[e], e); //如果出边所连另一个结点被访问且没被加入堆,将其加入
}
}
}
}
}

相关文章

SPFA学习笔记 | Ender’s blog

Floyd学习笔记 | Ender’s blog