最短路问题
- 求从s到t权值和最小的路径
- Floyd 算法：
- 多源最短路，求出所有点对的最短路长度
- 时间复杂度：(O(n^3))
- Dijkstra 算法：
- 单源最短路，求出某个点s到所有点的最短路长度
- 时间复杂度：(O(n^2)/O(mlogn))
- 无法处理负权
- SPFA 算法，即队列优化的Bellman-Ford 算法：
- 单源最短路，求出某个点s到所有点的最短路长度
- 时间复杂度：声称为(O(m)),最坏(O(nm)),容易卡到最坏
- 可以处理负权边，可以判断负环
Floyd
- 设(d[i][j][k])为从(i)到(j)，仅通过编号为(1 - k)的中间节点的最短路径距离
- (d[i][j][k] = min(d[i][j][k - 1], d[j][k][k - 1] + d[k][j][k - 1]))
- 初始值(d[i][j][0])为两点之间边权值，未连通为(INF)
- 从(1)到(n)枚举(k)，然后枚举((i, j))
- 为了方便可以不开第三维，在原地迭代--(d[i][j] = min(d[i][j], d[i][k] + d[k][j]))
代码
int d[MAXN][MAXN];
void Floyd(){
for(int k = 1; k <= n; ++k){
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
if(i != j && i != k && j != k)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
}
单源最短路
- 维护一个(dis[MAXN])数组，(dis[i])代表(s)到(i)的最短路径长度
- (dis[s] = 0)，其他为(INF)
- 松弛操作：通过某条路径更新(dis[v])的值
- (if(dis[v] > dis[u] + e.dist) dis[v] = dis[u] + e.dist)
- 尝试使用(s)到(u)的最短路加上边((u, v))的长度来更新(s)到(v)的最短路
SPFA
- Bellman-Ford：对整张图进行n - 1次松弛，每次枚举每条边进行松弛，最后一定能得出最优解
- SPFA：在上述过程中避免无意义的松弛
- 只有成功的松弛操作才会对那个点产生影响，所以使用队列维护等待松弛的点，每次取出一个点进行松弛，对于所有松弛成功的点加入队列
- 判负环：某个点松弛了n次，说明有负环
代码
bool vis[N];
queue<int> q;
void SPFA(int s){
memset(dist, 0x3f, sizeof(dist));
d[s] = 0;
q.push(s);
vis[s] = true;
while(!q.empty()){
int u = q.front(); q.pop();
vis[u] = false;
for(int i = head[u]; i; i = edge[i].nxt){
int v = edge[i].v;
int w = edge[i].w;
if(dist[u] + w < d[v]){
d[v] = d[u] + w;
if(!vis[v]){
q.push(v);
vis[v] = true;
}
}
}
}
}
Dijkstra
-
起点作为已访问集合的第一个点，并更新相连的点的dis
-
找到未被访问的dis最小的点，标记访问，用这个点更新相连的点dis
-
重复上述过程直到所有的点均被访问
-
问题在于“找到未被访问的dis最小的点”这一步，两种不同的实现方法会带来两种复杂度
-
枚举每个点
-
当点u的距离更新时，将(dis[u], u)插入堆中，这样堆中可能有多个u，此时取出后面的点时，会发现u已经被访问过不再处理
代码
void Dijkstra(int s){
memset(dist, 0x3f, sizeof(dist));
dist[s] = 0;
q.push(mk(dist[s], s));
while(!q.empty()){
int u = q.top().second;
int d = q.top().first; q.pop();
if(d > dist[u]) continue;
for(int i = head[u]; i; i = edge[i].nxt){
int v = edge[i].v;
int w = edge[i].w;
if(dist[u] + w < dist[v]){
dist[v] = dist[u] + w;
q.push(mk(dist[v], v));
}
}
}
}