单源最短路

一. 没有负权边:两个版本的迪杰斯特拉算法

迪杰斯特拉算法：单源最短路中，我们循环n次是确定n个点的最短路径，内部首先确定出当前距离最小的点，然后用这个点更新每个点的距离

朴素版的迪杰斯特拉算法O(n^2): 稠密图

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=510;
int g[N][N];
int dist[N];
bool st[N];
int n,m;
int dijkstra()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    for(int i=0;i<n;i++)
    {
        int t=-1;
        for(int j=1;j<=n;j++)
        {
            if(!st[j]&&(t==-1||dist[t]>dist[j]))
                t=j;
        }//找到当前距离最小的点
        st[t]=true;
        for(int j=1;j<=n;j++)
        {
            dist[j]=min(dist[j],dist[t]+g[t][j]);
        }
    }
    if(dist[n]==0x3f3f3f3f)return -1;
    else return dist[n];
}
int main()
{
    cin>>n>>m;
    memset(g,0x3f,sizeof g);
    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b]=min(g[a][b],c);
    }
    cout<<dijkstra();
    return 0;
}

堆优化版的迪杰斯特拉算法O(mlogn): 稀疏图

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N=1000010;
int h[N],e[N],ne[N],w[N],idx;
int dist[N];
bool st[N];
int n,m;
void add(int a,int b,int c)
{
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
int dijkstra()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    priority_queue<PII,vector<PII>,greater<PII>>q;
    q.push({0,1});
    while(q.size())
    {
        auto t=q.top();
        q.pop();
        int ver=t.y,distance=t.x;
        if(st[ver])continue;
        st[ver]=true;
        for(int i=h[ver];~i;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>w[i]+distance)
            {
                dist[j]=w[i]+distance;
                q.push({dist[j],j});
            }
        }
    }
    if(dist[n]==0x3f3f3f3f)return -1;
    else return dist[n];
}
int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }
    cout<<dijkstra();
    return 0;
}

在这里面我们优化的只是寻找最短的边所连接的点，其他还是老样子

二.有负权边

一.bellman_ford算法

算法简介：就是将所有的边遍历一边，更新最短距离，然后这里要注意的是我们在更新的时候如果用同一个数组更新会导致链式反应，因此我们需要重新开一个数组专门记录上一次更新后距离情况
在算法中,第一层循环的含义是走不超过k条边后最短距离的情况

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=510,M=10010;
struct edge
{
    int a,b,w;
}edges[M];
int dist[N],backup[N];
int n,m,k;
void bellman_ford()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    for(int i=0;i<k;i++)//这里之所以循环k-1次是因为，倘若是一条链，也就是最坏情况，那么k个点就会有k-1个边，也就是说要走k-1轮
    {
        memcpy(backup,dist,sizeof dist);
        for(int j=0;j<m;j++)//这里尝试对所有边进行松弛操作
        {
            auto t=edges[j];
            dist[t.b]=min(dist[t.b],backup[t.a]+t.w);//注释一
        }
    }
}
int main()
{
    cin>>n>>m>>k;
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        edges[i]={a,b,c};
    }
    bellman_ford();
    if(dist[n]>0x3f3f3f3f/2)puts("impossible");
    else cout<<dist[n]<<endl;
    return 0;
}

注释一:我们由这个式子可知:dist[b]<=dist[a]+distance,这个式子叫做三角不等式

二.spfa算法

spfa算法是bellman_ford算法的一个优化,其优化就是用队列存储被更新的点,因为只有前驱点距离变化了,后继的点才会发生改变
因为只要发生了松弛操作就会重新进入队列，因此我们可以开一个数组来记录以当前点为终点的边的数量，进而来判断是否有负环

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N=100010;
int h[N],e[N],ne[N],w[N],idx;
int dist[N];
bool st[N];//这里队列用来存储被更新的点
int n,m;
void add(int a,int b,int c)
{
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
void spfa()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    queue<int> q;
    q.push(1);
    st[1]=true;
    while(q.size())
    {
        int t=q.front();
        q.pop();
        st[t]=false;
        for(int i=h[t];~i;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[t]+w[i])
            {
                dist[j]=dist[t]+w[i];
                if(!st[j])
                {
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }
    spfa();
    if(dist[n]==0x3f3f3f3f)puts("impossible");
    else cout<<dist[n]<<endl;
    return 0;
}

我感觉迪杰斯特拉算法是对点进行操作的,而bellman_ford算法和spfa算法则是对边进行操作的

判断负环的方法就是运用抽屉原理,我们只需要新开一个数组进行记录每个点的边数,如果当前点被更新的次数大于等于总点数,那么就是说存在了负环,这里的负环是所有路径上的,所以我们最开始初始化队列的时候需要将所有的点都加入

多源汇最短路

floyd算法(仅此一个)O(n^3)

三重循环,第一重循环表示经过的点,第二三重循环表示起点和终点

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=210,M=20010;
int dist[N][N];
int n,m,k;
void floyd()
{
    for(int k=1;k<=n;k++)//这里k一定要在最外面，表示插入的点
    {
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
    }
}
int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i==j)dist[i][j]=0;
            else dist[i][j]=0x3f3f3f3f;
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        dist[a][b]=min(dist[a][b],c);
    }
    floyd();
    while(k--)
    {
        int a,b;
        cin>>a>>b;
        if(dist[a][b]>0x3f3f3f3f/2)puts("impossible");
        else cout<<dist[a][b]<<endl;
    }
    return 0;
}