Dijkstra算法

概念

Dijkstra算法是一种解决单源最短路径问题的贪心算法。

朴素版Dijkstra算法

思想：
朴素版Dijkstra算法是一种贪心算法，通过维护每个节点的当前最短距离来逐步确定从起始节点到其他节点的最短路径。在每一步中，选择当前未被标记的节点中距离最短的节点进行标记，并更新其邻居节点的距离值。

概念：

  1. 距离值（distance）： 表示从起始节点到某个节点的当前已知最短路径长度。
  2. 标记集合（visited）： 用于标记已确定最短路径的节点。

过程：

  1. 初始化： 将起始节点的距离值设为0，其他节点的距离值设为无穷大（表示尚未确定最短路径），标记集合为空。
  2. 选择最短路径节点： 从未被标记的节点中选择距离值最小的节点，标记为已访问。
  3. 更新邻居节点： 对于已访问节点的每个相邻节点，计算通过当前节点到达该相邻节点的路径长度，并更新相邻节点的距离值。
  4. 重复步骤2和3： 重复选择最短路径节点和更新邻居节点的步骤，直到所有节点都被标记为已访问。
  5. 最终结果： 每个节点的距离值即为从起始节点到达该节点的最短路径长度。

注意： 朴素版Dijkstra算法的时间复杂度相对较高，特别是在稠密图中，因为在每一步中都需要线性搜索未被标记的节点。为了提高效率，引入优先队列的版本能够更快地选择最短路径节点。

img

代码部分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
const int N = 3010;
int n,m,g[N][N];//邻接矩阵
int d[N],st[N];//距离数组，标记数组
void dji(int s = 1){
	memset(d,0x3f,sizeof d); d[s] = 0;
	for(int i=1;i<=n;++i)
	{
		int x = 0;
		for(int j=1;j<=n;++j)
		{
			if(st[j]) continue;
			if(x == 0|| d[j] < d[x]) x = j;
		}
		st[x] = 1;
		for(int j=1;j<=n;++j) d[j] = min(d[j],d[x] + g[x][j]);
	}
}
int main()
{
	cin >> n >> m;
	memset(g,0x3f,sizeof g);
	for(int i=1;i<=m;++i)
	{
		int x,y,w;cin >> x >> y >> w;
		g[x][y] = min(g[x][y],w);//考虑重边
		g[y][x] = min(g[y][x],w);//无向图
	}
	dji();
	if(d[n] == INF) cout << -1 << endl;
	else cout << d[n] << endl;
	return 0;
}

Dijkstra算法堆优化

思想：
Dijkstra算法的一种优化方式是引入堆（优先队列）数据结构，以提高在每一步中选择最短路径节点的效率。这种堆优化的Dijkstra算法能够更快地确定最短路径，特别在大规模图中表现更为出色。

概念：

  1. 距离值（distance）： 表示从起始节点到某个节点的当前已知最短路径长度。
  2. 标记集合（visited）： 用于标记已确定最短路径的节点。
  3. 优先队列（priority queue）： 存储待处理节点，并按距离值大小排序，以便每次选择最短路径节点。

过程：

  1. 初始化： 将起始节点的距离值设为0，其他节点的距离值设为无穷大（表示尚未确定最短路径），将所有节点加入优先队列。
  2. 选择最短路径节点： 从优先队列中选择距离值最小的节点，标记为已访问。
  3. 更新邻居节点： 对于已访问节点的每个相邻节点，计算通过当前节点到达该相邻节点的路径长度，并更新相邻节点的距离值。
  4. 重复步骤2和3： 重复选择最短路径节点和更新邻居节点的步骤，直到所有节点都被标记为已访问。
  5. 最终结果： 每个节点的距离值即为从起始节点到达该节点的最短路径长度。

注意: Dijkstra算法在正权重图（权重不能为负）上表现良好，但不适用于存在负权重边的图。如果图中存在负权重边，可以考虑使用Bellman-Ford算法。

代码部分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
vector<int> dis(n + 1,0x3f3f3f3f);
auto dijkstra = [&](int s = 1) ->void
{
	int y,w;
	using PII = pair<int,int>;
	priority_queue<PII,vector<PII>,greater<PII> > q;
	q.emplace(0,s);
	dis[s] = 0;
	vector<int> st(n + 1);
	while(q.size())
	{
		int x = q.top().second;
		q.pop();
		if(st[x]) continue;
		st[x] = 1;
		for(auto el : h[x])
		{
			tie(y,w) = el;
			if(dis[y] > dis[x] + w)
			{
				dis[y] = dis[x] + w;
				q.emplace(dis[y],y);
			}
		}
	}
};

正确性证明

为什么dijkstra算法这样的贪心策略是正确的？转载自

首先，Dijkstra算法成立的前提条件是不存在负权的边。这意味着任何一条路径，从起点开始到路径中每个点的距离都是依次递增的。

所以，按照递增的顺序来依次计算出最短路径，也就是Dijkstra算法了。

为了简单起见，我们可以认为所有的边权都是正值。如果有边的权值为0，则这个边的两个顶点到源点的最短距离一定相等，可以把它们看成是同一个顶点，这样只要证明了边权值为正值的情况，也就能进一步推广到有边权值为0的情况。

当我们计算最短路径的时候，源点到任意一个点的最短距离，要么是源点到它的某条边的长度，要么是源点到另一个点的最短距离距离，再加上另一个点到这个点的边的长度，写成公式就是：

$$
d(i) = \min{D(s, i), \min_{j \ne i} d(j) + D(j, i)}
$$

注意到我们有 $(D(j, i) > 0)$，假如我们已经提前知道了各个 $d(i)$ 的大小顺序，那么比该顶点的最短路径距离更长的点就不用考虑了，改写成：

$$
d(i) = \min{D(s, i), \min_{d(j) < d(i)} d(j) + D(j, i)}
$$

假想我们已经提前将 $d(i)$ 排好了序，除了源点以外，最近的是 $n_0$，然后是 $n_1$，然后是 $n_2$，也就是:

$$
d(n_0) \leq d(n_1) \leq d(n_2) \leq … \leq d(n_m)
$$

那么我们的公式即可变成:

$$
d(n_k) = \min{D(s, n_k), \min_{j < k} d(n_j) + D(n_j, n_k)}
$$

假如说我们现在已经知道了最短距离最小的前 $k$ 个节点 ${n_0, n_1, …, n_{k−1}}$——特别的，$k = 0$ 的时候，这些节点的集合是个空集。当然它们的最短距离也根据上面的式子算了出来。我们希望接下来，通过这些信息找到 $n_k$，并且计算出 $d(n_k)$。

我们回到最早的式子中：

$$
d(i) = \min{D(s, i), \min_{j \ne i} d(j) + D(j,i)}
$$

如果在求最小值的第二项中，去掉一些项，那么得到的结果有可能会比原表达式大，但不可能比原表达式小（因为是求最小值的运算）。也就是对于 $i \notin {n_0, n_1, …, n_{k-1}}$，有：

$$
d(i) \le \min{D(s, i), \min_{j \in {n_0, n_1, …, n_{k-1}}} d(j) + D(j,i)}
$$

同时有：

$$
d(n_k) = \min{D(s, n_k), \min_{j \in {n_0, n_1, …, n_{k-1}}} d(j) + D(j,n_k)}
$$

也就是说，对于最后的 $n_k$ 来说，前面的式子会取等号。我们又知道 $n_k$ 是剩下节点中最短距离最小的。

也就是 :

$$
n_k = \arg \min_i d(i) = \arg \min_i \min{D(s, i), \min_{j \in {n_0, n_1, …, n_{k-1}}} d(j) + D(j,i)}
$$

第二个等号是因为我们将求最值表达式中不是最小的项替换成了比较大的项，而最小的项保持不变，因此最小值不变。这个最后的表达式就是Dijkstra算法。

在实际使用的时候，注意到这个式子可以改写成：

$$
\min{D(s,i), \min_{j \in {n_0, n_1, …, n_{k-1}}} d(j) + D(j,i)}
= \min{d(n_{k-1}) + D(n_{k-1},i), \min{D(s,i), \min_{j \in {n_0, n_1, …, n_{k-2}}} d(j) + D(j,i)}}
$$

第二项在上一轮就已经算出来了，所以每一轮只需要用最新加入的节点放缩一次就可以了。

直观来说，如果我们已经求出了k个离源点距离最近的点，以及它们各自的距离，那么到源点距离第k+1近的点，它到源点的最短路径只能经过这前k个点——如果经过了其他点，那么这个其他点显然离源点更近，那这个点一定不是第k+1近了。既然只经过这前k个点，那么只用这前k个点放缩就可以找到那个最短路径了。再加上前k-1个点上一轮已经放缩过，所以每一轮只需要用新加入的节点进行放缩就行了。

算法 > 图论
#algorithm #图论基础 #最短路
Dijkstra算法
http://pikachuxpf.github.io/posts/c4fedc02/
作者
Pikachu_fpx
发布于
2024年1月18日
许可协议