Floyd-Warshall
原理
分别枚举起始点i,中转点k,目标点j
如果e[i][k]+e[k][j] < e[i][j]
更新e[i][j]
的值
中转点枚举在最外层
模版
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define N 100
#define INF 0x7fffff
using namespace std;
int main()
{
int g[N][N] = {};
for(int i=0; i<=N; ++i)
for(int j=0; j<=N; ++j)
if(i != j)
g[i][j] = INF;
else
g[i][j] = 0;
int n, m;
scanf("%d%d", &n, &m);
int u, v, w;
for(int i=0; i<m; ++i)
{
scanf("%d%d%d", &u, &v, &w);
g[u][v] = w;
}
for(int k=1; k<=n; ++k)
for(int i=1; i<=n; ++i)
for(int j=1; j<=n; ++j)
g[i][j] = min(g[i][j], g[i][k]+g[k][j]);
printf("%d", g[1][n]);
return 0;
}
Dijkstra
原理
假设起点为1号节点
初始化1号节点的出边权值至dis数组(估计值)
找当前dis中最小边权(确定值)(假设为2号节点)
以2号节点的出边边权更新dis数组,若e[2][i]+dis[2] < dis[i]
,就更新dis[i]
以此类推,进行松弛
每次找离源点最近的点,然后依次进行扩展
用book数组进行标记是否使用
模版
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define N 100
#define INF 0x7ffff
using namespace std;
int main()
{
int e[N][N], dis[N], book[N];
int n, m;
scanf("%d%d", &n, &m);
for(int i=1; i<=n; ++i)
for(int j=1; j<=n; ++j)
if(i == j)
e[i][j] = 0;
else
e[i][j] = INF;
int u, v, w;
for(int i=1; i<=m; ++i)
{
scanf("%d%d%d", &u, &v, &w);
e[u][v] = w;
}
for(int i=1; i<=n; ++i)
dis[i] = e[1][i];
memset(book, 0, sizeof(book));
book[1] = 1;
int minn = INF, k;
for(int i=1; i<=n; ++i)
{
minn = INF;
for(int j=1; j<=n; ++j)
if(!book[j] && dis[j]<minn)
{
minn = dis[j];
k = j;
}
book[k] = 1;
for(int j=1; j<=n; ++j)
if(e[k][j]<INF)
dis[j] = min(dis[j], dis[k]+e[k][j]);
}
for(int i=1; i<=n; ++i)
printf("%d ", dis[i]);
return 0;
}
Bellman-Ford
原理
进行n-1轮松弛(详见Dijkstra)
没啥好说的
模版
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define N 100
#define INF 0x7ffff
using namespace std;
int main()
{
int dis[N], n, m, u[N], v[N], w[N];
scanf("%d%d", &n, &m);
for(int i=1; i<=m; ++i)
scanf("%d%d%d", &u[i], &v[i], &w[i]);
for(int i=1; i<=n; ++i)
dis[i] = INF;
dis[1] = 0;
int check = 0; //检查dis是否改变
for(int i=1; i<=n-1; ++i)
{
check = 0;
for(int j=1; j<=n; ++j)
if(dis[v[j]] > dis[u[j]]+w[j])
{
dis[v[j]] = dis[u[j]]+w[j];
check = 1;
}
if(!check) //优化
break;
}
int flag = 0;
for(int i=1; i<=m; ++i)
if(dis[v[i]] > dis[u[i]]+w[i])
flag = 1;
if(flag)
printf("有负权回路");
else
for(int i=1; i<=n; ++i)
printf("%d ", dis[i]);
return 0;
}
SPFA
原理
用队列优化的Bellman-Ford
思想差不多(Bellman-Ford+BFS)
不用像BFS一样打标记(敲黑板)
不会邻接表的参考我的这篇博文
模版(邻接表)
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define N 100
#define INF 0x7ffff
using namespace std;
int main()
{
int n, m;
int u[N], v[N], w[N];
scanf("%d%d", &n, &m);
int first[n+1], next[m+1];
int dis[N] = {}, book[N] = {}, que[N] = {}, head = 1, tail = 1;
for(int i=1; i<=n; ++i)
dis[i] = INF;
dis[1] = 0;
for(int i=1; i<=n; ++i)
first[i] = -1;
for(int i=1; i<=m; ++i)
{
scanf("%d%d%d", &u[i], &v[i], &w[i]);
next[i] = first[u[i]];
first[u[i]] = i;
}
que[tail++] = 1;
book[1] = 1;
int k;
while(head < tail)
{
k = first[que[head]];
while(k != -1)
{
if(dis[v[k]] > dis[u[k]]+w[k])
{
dis[v[k]] = dis[u[k]]+w[k];
if(book[v[k]] == 0)
{
que[tail++] = v[k];
book[v[k]] = 1;
}
}
k = next[k];
}
book[que[head]] = 0;
head++;
}
for(int i=1; i<=n; ++i)
printf("%d ", dis[i]);
return 0;
}
算法比较
Floyd-Warshall | Dijkstra | Bellman-Ford | SPFA | |
---|---|---|---|---|
空间复杂度 | O() | O(M) | O(M) | O(M) |
时间复杂度 | O() | O((M+N)logN) | O(NM) | 最坏也是O(NM) |
适用情况 | 稠密图,与顶点关系密切 | 稠密图,与顶点关系密切 | 稀疏图,与边关系密切 | 稀疏图,与边关系密切 |
负权 | Y | N | Y | Y |
负权边 | Y | N | Y | Y |
负权回路判定 | N | N | Y | Y |