最短路
前置
在本文最短路模块中, \(n\) 代表点数, \(m\) 代表边数。
图分稠密图和稀疏图,稀疏图 \(m≈n×10\) ,稠密图 \(m≈n^2\) 。
对于每个算法的代码,写在函数内的是核心代码。
floyd
floyd 是一种基于动态规划思想的全源最短路算法,可以解决负权边,复杂度 \(\operatorname{O(n^3)}\) 。
思路
状态表示:
设 \(dis_{(i,j)}\) 为 \(i\) 到 \(j\) 的的短距离。
三层循环:
- 第一层 \(k\) 枚举阶段,表示当前对于每个点已经确定离它 \(k\) 个点的最短路径。
- 第二层 \(i\) 枚举起点,表示从第 \(i\) 个点开始的最短路径。
- 第三层 \(j\) 枚举终点,表示从第 \(j\) 个点结束的最短路径。
状态转移:
一条路有两种走法:
- 直接从 \(i\) 走到 \(j\) : \(dis_{(i,j)}\) 。
- 先从 \(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 算法的瓶颈在于寻找全局最小值
标签:rll,图论,read,ll,初步,dijkstra,dis,define From: https://www.cnblogs.com/wangxuzhou-blog/p/17157859.html