Dijkstra学习笔记

Dijkstra学习笔记

介绍

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

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

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

实现

存图

这里使用结构图进行存图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const int MAXN = 100010;
const int MAXM = 200010;

struct Edge {
int from, to, dist;
Edge() {} //构造函数,用于快速传入数据
Edge(int _from, int _to, int _dist): from(_from), to(_to), dist(_dist) {}
};

int etop = 1; //表示存图时边的编号(从1开始)
Edge ed[MAXM]; //结构体Edge类型数组,用于保存边i的信息ed[i]
int he[MAXN], ne[MAXM]; //he[i]表示结点i的第一条出边的编号,ne[i]表示编号为i的边的下一条边
//如果i的下一条边ne[i]的编号为0,则表示没有下一条边

inline void insert(int u, int v, int w) { //邻接表 单项边存边
ed[etop] = Edge(u, v, w); //调用结构体构造函数进行存边
ne[etop] = he[u]; //将新加入的边从表头插入
he[u] = etop++; //表头更新
}

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 = he[now]; i;i = ne[i]) { //枚举出边
Edge& e = ed[i];
if(d[e.to] > d[now] + e.dist) { //松弛
d[e.to] = d[now] + e.dist;
q.push(make_pair(d[e.to], e.to); //如果出边所连另一个结点被访问且没被加入堆,将其加入
}
}
}
}
}

相关文章

SPFA学习笔记 | Ender’s blog

Floyd学习笔记 | Ender’s blog

感谢支持,您的支持将是我原创的动力!