最短路

前置

在本文最短路模块中， \(n\) 代表点数， \(m\) 代表边数。

图分稠密图和稀疏图，稀疏图 \(m≈n×10\) ，稠密图 \(m≈n^2\) 。

对于每个算法的代码，写在函数内的是核心代码。

floyd

floyd 是一种基于动态规划思想的全源最短路算法，可以解决负权边，复杂度 \(\operatorname{O(n^3)}\) 。

思路

状态表示：

设 \(dis_{(i,j)}\) 为 \(i\) 到 \(j\) 的的短距离。

三层循环：

1. 第一层 \(k\) 枚举阶段，表示当前对于每个点已经确定离它 \(k\) 个点的最短路径。
2. 第二层 \(i\) 枚举起点，表示从第 \(i\) 个点开始的最短路径。
3. 第三层 \(j\) 枚举终点，表示从第 \(j\) 个点结束的最短路径。

状态转移：

一条路有两种走法：

1. 直接从 \(i\) 走到 \(j\) ： \(dis_{(i,j)}\) 。
2. 先从 \(i\) 走到 \(k\) 再从 \(k\) 走到 \(j\) ： \(dis_{(i,k)}+dis_{(k,j)}\) 。

floyd 算法的思路就是，对于所有的 \(i,j,k\) ，取这两条路的最短距离。

dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);

代码

#include <bits/stdc++.h>
#define ll long long
#define rll register ll
#define cll const ll
#define N 1005
using namespace std;
inline ll read()
{
    rll x=0;bool f=1;register char c=getchar();
    while(c<48||c>57){if(c=='-') f=0;c=getchar();}
    while(c>=48&&c<=57){x=x*10+(c^48);c=getchar();}
    return f?x:-x;
}
inline void write(ll x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+48);
}
cll n=read();
ll m=read(),a,b,c,dis[N][N];
inline void floyd()
{
    for(rll k=1;k<=n;k++)
        for(rll i=1;i<=n;i++)
            for(rll j=1;j<=n;j++)
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
int main()
{
    memset(dis,0x3f,sizeof dis);
    for(rll i=1;i<=n;i++) dis[i][i]=0;
    //初始化所有变为正无穷，每个点到自己的最短距离为 0
    while(m--)
    {
        a=read(),b=read(),c=read();
        dis[a][b]=min(dis[a][b],c);
        dis[b][a]=min(dis[b][a],c);
        //无向边，双向连边即可
        //如有重边，保留最小值即可
    }
    floyd();
    for(rll i=1;i<=n;i++)
    {
        for(rll j=1;j<=n;j++)
        {
            if(dis[i][j]>=0x3f3f3f3f3f3f3f3f) cout << "-1";
            else write(dis[i][j]),putchar(' ');
            //如果为正无穷就无法走到
            //注意 memset 是以字节赋值的，因此对于 long long 是 0x3f3f3f3f3f3f3f3f
        }
        putchar('\n');
    }
    return 0;
}

dijkstra

dijkstra 是一种基于贪心思想的单源最短路算法，不能解决负权边，朴素版复杂度 \(\operatorname{O(n^2)}\) ，堆优化版复杂度 \(\operatorname{O(mlogn)}\) 。

思路

执行 \(n-1\) 轮循环，每轮循环先寻找全局最小值，再用全局最小值更新起点到每个点的距离 \(dis_{i}\) 。
至于为什么是 \(n-1\) 轮，是因为跑完 \(n-1\) 轮后，点只剩下一个，最短路已经确定。

代码

#include <bits/stdc++.h>
#define ll long long
#define rll register ll
#define cll const ll
#define N 505
#define M 100005
using namespace std;
inline ll read()
{
    rll x=0;bool f=1;register char c=getchar();
    while(c<48||c>57){if(c=='-') f=0;c=getchar();}
    while(c>=48&&c<=57){x=x*10+(c^48);c=getchar();}
    return f?x:-x;
}
inline void write(ll x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+48);
}
cll n=read();
ll m=read(),dis[N],g[N][N];
bool flag[N];//flag[i] 表示每个点是否被取用过
inline void dijkstra()
{
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;
    for(rll i=0;i<n;i++)
    {
        rll t=-1;
        for(rll j=1;j<=n;j++)
            if(!flag[j]&&(t==-1||dis[j]<dis[t])) t=j;
        //寻找全局最小值
        flag[t]=1;
        for(rll j=1;j<=n;j++) dis[j]=min(dis[j],dis[t]+g[t][j]);
        //用全局最小值更新剩余的点
    }
}
int main()
{
    memset(g,0x3f,sizeof(g));
    while(m--)
    {
        cll a=read(),b=read(),c=read();
        g[a][b]=min(g[a][b],c);//重边取最小值
    }
    dijkstra();
    if(dis[n]>=0x3f3f3f3f3f3f3f3f) cout << "-1";
    else write(dis[n]);
    //如果距离为正无穷说明不存在路径
    return 0;
}

堆优化 dijkstra

我们发现，朴素 dijkstra 算法的瓶颈在于寻找全局最小值