Dijkstra及其复杂度证明

本文主要围绕易混淆的复杂度分析进行讨论

另外其实这个不叫迪杰斯特拉，这个叫/ˈdɛɪkstra/ qwq

---

一、前置知识

先放几个简单概念

无向图：图中所有的边都是两端可达的，也就是可以从任意一端通过这条边

有向图：图中所有的边都是单向的，有一个起点和一个终点，方向为起点指向终点

重边：两个结点间多条存在完全一样的边，通常它们可能拥有不同的权重或属性

自环：起点和终点相同的边

简单图：图中不存在自环和重边，显然一定存在两个结点的度数相同

多重图：存在自环或重边

更多内容可以参考这里 ，这里只介绍了一些对本文有用的概念

---

二、时间复杂度分析

给定一张具有非负权重的图和一个源点 $s$ （起点），问结点 $t$ 与 $s$ 的最短距离是多少

设图中的结点数为 $n$ ，边数为 $m$ ，$n\le m$

算法流程：

0. $\text{dis[s]=0}\wedge \forall u\in V\backslash S,\text{dis[}u\text{]}=+\infty$

1. 从未确定最短路的点集 $T$ 中找到一个结点满足其最短路长度最小

2. 将已确定最短路的点集 $S$ 的所有出边进行松弛操作

3. 如果 $T\ne \varnothing$ ，重复1,2操作

1. 朴素dijkstra

操作1复杂度为 $O(n)$ ，操作2复杂度为 $O(n)$ ，每条都会被松弛一次

因此总时间复杂度为 $O(m+n^2)$

2.优先队列优化

显然操作1可以优化

考虑一般多重图，使用优先队列优化存在弊端

对于队首的元素，至多遍历 $d_i$ 条边 ，$\sum d_i=m$

注意到一次操作2中，同一结点可能入队多次，则时间复杂度为 $O(m)$

假设按某种固定顺序遍历出边，每次松弛操作都会使被松弛结点入队

因为存在重边，考虑构造重边以权重大小降序排列，即 $w(e_{k-1})\ge w(e_k),k\in \mathbb{Z}\wedge k\in [1,d_i]$

这样最坏可以做到 $O(m)$

因此找最短路最小的结点时间为 $O(\log m)$

每个结点至少被遍历一次

则总时间复杂度为 $O\left((n+m)\log m\right)$

优先队列优化的代码

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)$ 对应堆上的哪个节点（当然你也可以写个平衡树）

这样总时间复杂度为 $O\left((n+m)\log n\right)$

不过一般是反向优化，因为常数巨大并且 $\mathcal{O}(\log n)$ 和 $\mathcal{O}(\log m)$ 在稀疏图的情况下相差很小。

4.斐波那契堆优化

原理同二叉堆，这个理论上更快但是更难写且常数很大，一般不使用

理论时间复杂度 $O(m+n\log n)$