ACM最短路

发表于 | 分类于 | 浏览
字数统计: 1k | 阅读时长 ≈ 4

最短路算法介绍及简略证明

公共前提

对于连通图$G=(V,E)$，$|V|=n$，$|E|=m$，$w_{i,j}$表示节点$i$和$j$间的权值，我们需要求得对于任意给定的节点$s$和$t$，$w_{s,t}$的最小值

$Floyd$算法

核心思路

对于任意两个节点$i$，$j$，若能找到一个节点$k$使得$w_{i,k}+w_{k,j}<w_{i,j}$，那么我们更新$w_{i,j}$的值为$w_{i,k}+w_{k,j}$，对于$\forall i,j,k \in [1,n]$，我们比较$w_{i,k}+w_{k,j}$和$w_{i,j}$的关系，最后$w_{s,t}$即为所求值

算法证明

首先考虑初始情况，对于节点$i$和$j$，要么联通（仅有$i$至$j$的一条边），要么不连通（权值为$\infty$），在第一次迭代更新时，若$\exists k$使得$w_{i,k}+w_{k,j}<w_{i,j}$，那么我们会将节点$k$加入到联通$i,j$的最短链中，在下一次迭代，我们又会更新$i,k$和$k,j$的中间节点，如此往复，最终我们会得到联通$i,j$的一条最短链，并且该链中任意两点间的距离均为最短，则此时$w_{s,t}$为所求

代码实现

1
2
3
4
5
6
for(int k = 1; k <= n; ++k) {
  for(int i = 1; i <= n; ++i) {
    for(int j = 1; j <= n; ++j) {
      W[i][j] = min(w[i][j], w[i][k] + w[k][j]);
  }
}

可以看出时间复杂度为$O(n^3)$

算法缺点

无法处理带有负权环的图，因为负权环中不存在最短路

$Dijkstra$算法

核心思路

我们维护一个节点集合$S$，集合中的点两两已确定最短路，我们每次找到与$S$中所有相邻点中距离起点$s$最近的节点$v$，设其父亲节点为$u$，并将其加入到集合$S$，并使得$w_{s,v}=w_{s,u}+w_{u,v}$，并更新$w_{s,i}=min(w_{s,i},w_{s,k}+w_{k,i})$

算法证明

该算法的原理基于以下前提：

对于一个顶点$u$的字段邻接边所连点$v$，必然不存在$k$使得$w_{u,v}>w_{u,k}+w_{k,v}$

很好理解，因为$w_{u,v} \leq w_{u,i}$，显然有$w_{u,v} \leq w_{u,k}$

那么每次迭代找到的$v$，$w_{s,v}=w_{s,u}+w_{u,v}$显然最小

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
bool vis[maxn];
int dis[maxn];
memset(vis, false, sizeof(vis));
memset(dis, 0x3f3f3f3f, sizeof(dis));
dis[s] = 0;
vis[s] = true;
for(int i = 1; i <= n; ++i) {
  int k = 0;
  int Min = 0x3f3f3f3f;
  for(int j = 1; j <= n; ++j) {
    if(!vis[j] && dis[j] < Min) {
      k = j;
      Min = dis[k];
    }
  }
  vis[k] = true;
  for(int j = 1; j <= n; ++j) {
    if(!vis[j] && dis[j] > dis[k] + W[k][j]]) {
      dis[j] = dis[k] + w[k][j];
    }
  }
}

可以看出朴素$Dijkstra$复杂度为$O(n^2)$，可以用堆将其优化到$O((n + m)log_{2}^{n})$，此处省略

算法缺点

不能处理负权图，因为负权边不满足前提条件

$Bellman-Ford$算法

核心思路

我们定义松弛操作为：

对于任意边$E(u,v)$，如果$w_{s,v}>w_{s,u}+w_{u,v}$，我们使得$w_{s,v}=w_{s,u}+w_{u,v}$

若所有顶点处理完毕后仍存在$w_{s,v}>w_{s,u}+w_{u,v}$，则说明存在负环

算法证明

该算法为$Floyd$的简化版，证明略

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//表示u[i], v[i]间的权值为w[i]
int u[maxn], v[maxn], w[maxn];
int dis[maxn];
memset(dis, 0x3f3f3f3f, sizeof(dis));
for(int k = 1; k <= n; ++k) {
  for(int i = 1; i <= m; ++i) {
    dis[v[i]] = min(dis[u[i]] + w[i]);
  }
}
bool loop = false;
for(int i = 1; i <= m; ++i) {
  if(dis[v[i]] > dis[u[i]] + w[i]) {
    loop = true;
    break;
  }
}

可以看出其时间复杂度为$O(nm)$

算法缺点

可以处理负权图和负权环，但是时间复杂度太高

$SPFA$算法

核心思路

由于$Bellman-Ford$复杂度过高，于是引入了队列优化的$Bellman-Ford$——$SPFA$