Dijkstra及其复杂度证明
没有摘要 qwq
Dijkstra及其复杂度证明
本文主要围绕易混淆的复杂度分析进行讨论
另外其实这个不叫迪杰斯特拉,这个叫/ˈdɛɪkstra/
qwq
一、前置知识
先放几个简单概念
无向图:图中所有的边都是两端可达的,也就是可以从任意一端通过这条边
有向图:图中所有的边都是单向的,有一个起点和一个终点,方向为起点指向终点
重边:两个结点间多条存在完全一样的边,通常它们可能拥有不同的权重或属性
自环:起点和终点相同的边
简单图:图中不存在自环和重边,显然一定存在两个结点的度数相同
多重图:存在自环或重边
更多内容可以参考这里 ,这里只介绍了一些对本文有用的概念
二、时间复杂度分析
给定一张具有非负权重的图和一个源点 s s s (起点),问结点 t t t 与 s s s 的最短距离是多少
设图中的结点数为 n n n ,边数为 m m m , n ≤ m n\le m n≤m
算法流程:
-
dis[s]=0 ∧ ∀ u ∈ V \ S , dis[ u ] = + ∞ \text{dis[s]=0} \land \forall u \in V\backslash S , \text{dis[}u\text{]}=+\infty dis[s]=0∧∀u∈V\S,dis[u]=+∞
-
从未确定最短路的点集 T T T 中找到一个结点满足其最短路长度最小
-
将已确定最短路的点集 S S S 的所有出边进行松弛操作
-
如果 T ≠ ∅ T\ne \varnothing T=∅ ,重复1,2操作
1. 朴素dijkstra
操作1复杂度为 O ( n ) O(n) O(n) ,操作2复杂度为 O ( n ) O(n) O(n) ,每条都会被松弛一次
因此总时间复杂度为 O ( m + n 2 ) O(m+n^2) O(m+n2)
2.优先队列优化
显然操作1可以优化
考虑一般多重图,使用优先队列优化存在弊端
对于队首的元素,至多遍历 d i d_i di 条边 , ∑ d i = m \sum d_i = m ∑di=m
注意到一次操作2中,同一结点可能入队多次,则时间复杂度为 O ( m ) O(m) O(m)
假设按某种固定顺序遍历出边,每次松弛操作都会使被松弛结点入队
因为存在重边,考虑构造重边以权重大小降序排列,即 w ( e k − 1 ) ≥ w ( e k ) , k ∈ Z ∧ k ∈ [ 1 , d i ] w(e_{k-1})\ge w(e_k),k\in\mathbb{Z}\land k\in[1,d_i] w(ek−1)≥w(ek),k∈Z∧k∈[1,di]
这样最坏可以做到 O ( m ) O(m) O(m)
因此找最短路最小的结点时间为 O ( log m ) O(\log m) O(logm)
每个结点至少被遍历一次
则总时间复杂度为 O ( ( n + m ) log m ) O\left((n+m)\log m\right) O((n+m)logm)
优先队列优化的代码
priority_queue<node> q;
void dijkstra(int st)
{
memset(d,0x3f,(n+1)*sizeof(int));
memset(vis,0,(n+1)*sizeof(int));
d[st]=0;q.push({st,0});
while(!q.empty())
{
int u=q.top().u;q.pop();
if(vis[u])continue;
vis[u]=1;
for(int i=head[u]; i; i=e[i].next)
{
int v=e[i].v,u=e[i].u;
if(d[v]>d[u]+e[i].w)
{
d[v]=d[u]+e[i].w;
q.push({v,d[v]});
}
}
}
}
3.二叉堆优化
由于每个点可能在遍历边时入队,而优先队列不支持修改操作
那么考虑用二叉堆(自己写一个)并记录每个 ( v , d v ) (v,d_v) (v,dv) 对应堆上的哪个节点(当然你也可以写个平衡树)
这样总时间复杂度为 O ( ( n + m ) log n ) O\left((n+m)\log n\right) O((n+m)logn)
不过一般是反向优化,因为常数巨大并且 O ( log n ) \mathcal{O}(\log n) O(logn) 和 O ( log m ) \mathcal{O}(\log m) O(logm) 在稀疏图的情况下相差很小。
4.斐波那契堆优化
原理同二叉堆,这个理论上更快但是更难写且常数很大,一般不使用
理论时间复杂度 O ( m + n log n ) O(m + n\log n) O(m+nlogn)
![Logo](https://devpress.csdnimg.cn/79de2bf0b7994defa4242ef90d5513fa.jpg)
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
所有评论(0)