笔记:最短路

Dijkstra

关于Dijkstra的朴素写法,当时没听,直接学了堆优化的思路

类似BFS,Dijkstra像是一种加权版的BFS并且可以进行贪心优化

这里的贪心优化指使用堆(小根堆)获取当然最短边,因为最短路一定是最短的,我们也优先选择最短边,这很好理解

还有一种新的概念叫作"松弛",对应代码是这样

if(dist[v]>d+w){
    dist[v]=d+w;
    pq.push({dist[v],v});
}

这表示如果发现一条更短路径时,就更新最短路估计值

#include<bits/stdc++.h>
using namespace std;
int n,m,s;
int main(){
    cin.tie(0);cin.sync_with_stdio(0);
    cin>>n>>m>>s;
    vector<pair<int,int> >g[n+1];
    vector<int>dist(n+1,INT_MAX);
    dist[s]=0;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        g[u].push_back({v,w});
    }
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int>>> pq;
    pq.push({0,s});
    while(!pq.empty()){
        int d=pq.top().first,u=pq.top().second;
        pq.pop();
        if(d!=dist[u])continue;
        for(auto e:g[u]){
            int v=e.first,w=e.second;
            if(dist[v]>d+w){
                dist[v]=d+w;
                pq.push({dist[v],v});
            }
        }
    }
    for(int i=1;i<=n;i++)cout<<dist[i]<<" ";
}

Floyd

Floyd 算法是一种动态规划求最短路的思路

我们逐步允许更多的“中间点”出现在路径里，看看能不能得到更短的路径。

设$$d[i][j] = \text{目前已知的从 i 到 j 的最短路径长度}$$

然后我们依次枚举一个“中转点” $k$：

$$d[i][j] = \min(d[i][j],\ d[i][k] + d[k][j])$$

意思是：如果 $i \to j$ 的直达路不如“绕一下 $k$”更短，那就更新答案。

    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);

SPFA

SPFA是Bellman–Ford算法的一种实现,更具体地,是Bellman-Ford 算法的队列优化版本

它可以求解带权图的 单源最短路径，可以处理 负权边（但不能有负权环）

SPFA 使用 队列 维护需要继续松弛的点：

1. 初始时源点入队。

2. 每次出队一个点 u，尝试对 u 的所有出边 (u,v,w) 进行松弛。

3. 如果 dist[v] 被更新，并且 v 不在队列里，就把 v 入队。

4. 队列空时结束。

这里的松弛可以用表达式

$$\text{if } dist[v] > dist[u] + w \;\; \Rightarrow \;\; dist[v] = dist[u] + w$$

它可以不断改进“最短路的估计值”,直到收敛为真正的最短路

#include<bits/stdc++.h>
using namespace std;
const int INF=1e9;
struct Edge{int v,w;};
int main(){
    int n,m,s;
    cin>>n>>m>>s;
    vector<vector<Edge>> g(n+1);
    for(int i=1;i<=m;i++){
        int u,v,w;cin>>u>>v>>w;
        g[u].push_back({v,w});
    }
    vector<int> dist(n+1,INF), inq(n+1,0);
    queue<int> q;
    dist[s]=0; q.push(s); inq[s]=1;
    while(!q.empty()){
        int u=q.front();q.pop();inq[u]=0;
        for(auto e:g[u]){
            if(dist[e.v]>dist[u]+e.w){
                dist[e.v]=dist[u]+e.w;
                if(!inq[e.v]){
                    q.push(e.v);
                    inq[e.v]=1;
                }
            }
        }
    }
    for(int i=1;i<=n;i++)cout<<dist[i]<<" ";
}

这里的inq数组表示当前这个点是否在队列里

我们知道队列里存储的是“等待松弛的点”

当某个点的 dist 被更新后,如果它 不在队列,就需要把它 加入队列;如果它已经在队列里,就不用重复加入,避免队列里出现同一个点的多份副本

复杂度分析