最短路总结

· · 算法·理论

多源最短路

Floyd:

时间复杂度：

O(N^3)

实现方式：

三重循环枚举起点，终点，中转点，然后进行松弛操作

代码模版：

void floyd(){
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
}
}
return;
}

其中，k是中转点

注意：中转点k的枚举必须写在最外层！

优点：

  1. 代码量小，好记，考试时遇到单源最短路的题目可以用Floyd骗一点分。

    缺点：

  2. 时间复杂度高，大概n到10^3就会超时。

    使用场景：

    处理多源最短路且n较小的时候用

    单源最短路

    Dijkstra:

    时间复杂度：

    普通版：O(N^2)

堆优化版：O(N*log(M))

实现方式：

每一次操作将当前长度最短的路径更新一个点，路径上的点数增加，路径长减少，由短的路->长的路

代码模版：

普通版：

int dis[500005],n,m,s;
bool vis[500005];
struct node{
int v,w;
};
vector<node>e[500005];
void dijkstra(){
for(int i=1;i<=n;i++)dis[i]=1e18;
dis[s]=0;
for(int i=1;i<=n;i++){
int minn=1e18,p;
for(int j=1;j<=n;j++){
if(vis[j]==0&&dis[j]<minn){
minn=dis[j];
p=j;
}
}
vis[p]=1;
for(int j=0;j<e[p].size();j++){
int v=e[p][j].v,w=e[p][j].w;
if(dis[v]>dis[p]+w)dis[v]=dis[p]+w;
}
}
}

堆优化版：


int n,m,s,dis[100005];
bool vis[100005];
struct node{
int v,w;
bool operator < (const node &b) const 
{
return b.w<w;
}
};
vector<node>e[100005];
priority_queue<node>pq;
void dijkstra(){
pq.push({s,0});
while(pq.size()){
node tt=pq.top();
pq.pop();
int u=tt.v;
if(vis[u]==1)continue;
vis[u]=1;   
for(int i=0;i<e[u].size();i++){
int v=e[u][i].v,w=e[u][i].w;
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
if(!vis[v])pq.push({v,dis[v]});
}
    }
}

}

>一般情况下，我们写代码用的都是堆优化版的dijkstra。
### 优点：
>1. 速度最快，能解决大多数单源最短路的题目
### 缺点：
>1. 无法解决负边权问题
>2. 代码较长，容易出错
### 使用场景：
>处理一般单源最短路

## Bellman-Ford:
### 时间复杂度：
>$O(NM)$
### 实现方式：
>枚举顶点和每一条边
### 代码模版：
```cpp
int n,k,dis[100005];
struct node{
    int u,v,w;
}e[100005];
void bellman_ford(){
    for(int i=1;i<=n;i++)dis[i]=1e18;
    dis[1]=0;
    while(1){
        bool flag=0;
        for(int i=1;i<=n;i++){
            int u=e[i].u,v=e[i].v,w=e[i].w;
            if(dis[v]>dis[u]+w){
                flag=1;
                dis[v]=dis[u]+w;
            }
        }
        if(!flag)break;
    }
}

优点：

  1. 好写
  2. 可以处理负环问题

    缺点：

  3. 速度较慢

    使用场景：

    处理负环问题，或数据较小的单源最短路

SPFA:

时间复杂度：

O(NM)

实现方式：

跟dijkstra差不多

代码模版：

const int N=1e5+7;
int n,m,s;
struct node{
int v,w;
};
vector<node>e[N];
queue<int>p;
int dis[N];
bool vis[N];
void spfa(){
for(int i=1;i<=n;++i){
vis[i]=0;
dis[i]=1e18;
}
dis[s]=0;
p.push(s);
vis[s]=1;
while(!p.empty()){
int u=p.front();
p.pop();
vis[u]=0;
for(int i=0;i<e[u].size();++i){
int v=e[u][i].v;
int w=e[u][i].w;
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
if(!vis[v]){
vis[v]=1;
p.push(v);
}
}
}   
}
return ;
}

优点：

  1. 随机数据速度快
  2. 可以处理负环问题

    缺点：

  3. 非随机数据的题目，SPFA容易被卡死

    使用场景：

    处理负环问题，或随机数据的单源最短路

附：Bellman-Ford和求负环(以P3385 【模板】负环为例)：

Bellman-Ford:

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int n,m,dis[100005],t;
struct node{
    int u,v,w;
}e[100005];
bool ballman(){
        for(int i=1;i<=n;i++)dis[i]=1e18;
        dis[1]=0;
    for(int j=1;j<n;j++){
        bool flag=0;
        for(int i=1;i<=m;i++){
            int u=e[i].u,v=e[i].v,w=e[i].w;
            if(dis[u]==1e18)continue;
            if(dis[v]>dis[u]+w){
                flag=1;
                dis[v]=dis[u]+w;
            }
        }
        if(!flag)break;
    }
    for(int i=1;i<=m;i++){
        int u=e[i].u,v=e[i].v,w=e[i].w;
        if(dis[u]==1e18)continue;
        if(dis[v]>dis[u]+w){
            return 1;
        }
    }return 0;
}
signed main(){

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n>>m;
        int cnt=0;
        for(int i=1;i<=m;i++){
            int u,v,w;
            cin>>u>>v>>w;
            e[++cnt]={u,v,w};
            if(w>=0)e[++cnt]={v,u,w};

        }
        m=cnt;
        if(ballman()){
            cout<<"YES\n";
        }else{
            cout<<"NO\n";
        }
    }

    return 0;
}