SPFA
以源点为起点BFS，对边进行逐一松弛，直至松弛至路径最短。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
using namespace std;
inline int read()
{
int l=0,w=1;
char ch=0;
while(ch<'0'||ch>'9')
{
if(ch=='-')
w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
l=(l<<3)+(l<<1)+(ch^'0');
ch=getchar();
}
return w*l;
}
int to[maxn],Next[maxn],head[maxn],wi[maxn],dis[maxn],n,m,s;
queue<int>q;
bool inQ[maxn];
int main()
{
memset(head,-1,sizeof(head));
int u,v,w,t=0;
n=read(),m=read(),s=read();
for(int i=1;i<=n;i++)
dis[i]=2147483647;
for(int i=1;i<=m;i++)
{
u=read(),v=read(),w=read();
wi[t]=w,to[t]=v,Next[t]=head[u],head[u]=t++;
}
dis[s]=0;
q.push(s);
inQ[s]=true;
while(!q.empty())
{
int x=q.front();
q.pop();
inQ[x]=false;
for(int i=head[x];i!=-1;i=Next[i])
if(dis[to[i]]>dis[x]+wi[i])
{
dis[to[i]]=dis[x]+wi[i];
if(!inQ[to[i]])
{
q.push(to[i]);
inQ[to[i]]=true;
}
}
}
for(int i=1;i<=n;i++)
printf("%d ",dis[i]);
return 0;
}
dijktra+堆优化
dijktra是每次将离源点最近的点取出，对所有该点出边进行松弛，堆优化则是用堆来储存距离，避免了每次重新排序的重复计算。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
using namespace std;
inline int read()
{
int l=0,w=1;
char ch=0;
while(ch<'0'||ch>'9')
{
if(ch=='-')
w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
l=(l<<3)+(l<<1)+(ch^'0');
ch=getchar();
}
return w*l;
}
int n,s,wi[maxn],to[maxn],Next[maxn],head[maxn],dis[maxn];
bool vis[maxn];
priority_queue<pp,vector<pp>,greater<pp> >q;
int main()
{
int m,u,v,w,t=0;
memset(head,-1,sizeof(head));
n=read(),m=read(),s=read();
for(int i=1;i<=n;i++)
dis[i]=2147483647;
for(int i=0;i<m;i++)
{
u=read(),v=read(),w=read();
wi[t]=w,to[t]=v,Next[t]=head[u],head[u]=t++;
}
dis[s]=0;
q.push(make_pair(0,s));
while(!q.empty())
{
pp u=q.top();
q.pop();
int x=u.second;
if(vis[x])
continue;
vis[x]=true;
for(int i=head[x];i!=-1;i=Next[i])
if(dis[to[i]]>dis[x]+wi[i])
dis[to[i]]=dis[x]+wi[i],q.push(make_pair(dis[to[i]],to[i]));
}
for(int i=1;i<=n;i++)
printf("%d ",dis[i]);
return 0;
}
Floyd
Floyd的本质是动态规划，dis[k][i][j]的意思是以1~k为中间点i→j的最短距离，情况可以分为经过k点和不经过k点，由此我们可以得出状态转移方程dis[k][i][j]=min(dis[k-1][i][j]，dis[k-1][i][k]+dis[k-1][k][j])。我们还可以将dis[k][i][j]直接写成dis[i][j],值得注意的是k循环应放在最外层。1
2
3
4
5for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(dis[i][k]+dis[k][j]<dis[i][j])
dis[i][j]=dis[i][k]+dis[k][j];