拓扑排序：
DFS实现
1
2
3
4
5
| dfs(int u){
for u 的所有邻点
seq<-u
}
|
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
|
bool topsort(){
queue<int> Q;
for(int i=1;i<=n;i++){
if(d[i]==0){
Q.push(i);
}
}
while(!Q.empty()){
int t=Q.front();ds.push_back(Q.front());
Q.pop();
for(int i=h[t];i!=-1;i=ne[i]){
int j=e[i];
d[j]--;
if(d[j]==0) Q.push(j);
}
}
int sz=ds.size();
return sz>=n;
}
|
最短路算法知识结构图
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
|
稠密图：一般边数m=n^2
稀疏图：边数m=n
Dijkstra基于贪心算法
Floyed基于动态规划
Bellman-Ford基于离散数学中的知识
朴素版Dijkstra算法
s={当前已经确定最短距离的点}
1.初始化
1
| dis[1]=0,dis[otherwise]=+∞
|
2.循环迭代(贪婪规则：更新当前还没有确定的点中距离最小的点）
1
2
3
4
| for(i:0~n)迭代循环n次
不在s中的距离最近的点->t
t->s
用t来更新其他点的距离(check(dis[x]>dis[t])
|
3.可确定每一个点到起点的最短距离了
存法：使用邻接矩阵(因为是稠密图)
朴素Dijstra解法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| int n,m;
int dis[MAXN],g[MAXN][MAXN];
bool st[MAXN];
int dijkstra(){
memset(dis,0x3f3f3f3f,sizeof(dis));
dis[1]=0;
for(int i=0;i<n;i++){
int t=-1;
for(int j=1;j<=n;j++)
if(!st[j] && (t==-1||dis[t]>dis[j]))
t=j;
if(t==n) break;
st[t]=true;
for(int j=1;j<=n;j++)
dis[j]=min(dis[j],dis[t]+g[t][j]);
}
if(dis[n]==0x3f3f3f3f) return -1;
return dis[n];
}
|
如果是稀疏图的话，对照上面的朴素Dijkstra，我们可以在这一步：
2.循环迭代(贪婪规则：更新当前还没有确定的点中距离最小的点）
1
2
3
4
| for(i:0~n)迭代循环n次
不在s中的距离最近的点->t ****************O(n^2)
t->s
用t来更新其他点的距离(check(dis[x]>dis[t]) ***O(mlogn)
|
此处使用堆来进行优化，直接借助于STL中的prority_queue或者手写堆（Python中的set）
bfs的迭代方式
1
2
3
4
5
| 1.先将(0,1)放入优先队列
2.while！empty:取堆顶元素并弹出,如果此点已经被更新过了则继续迭代。
否则用当前点来更新其他点(遍历邻接表)，记住，一定要将此点放入st[]数组来被标记
如果当前点距离大于从最近元素过来的距离，则更新dis[]并把j点放入优先队列；
3.最后结束的时候需要判断是否是孤立点，即是否为连通图
|
代码：
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
|
int n,m,idx;
int h[MAXN],e[MAXN],ne[MAXN],w[MAXN];
int dis[MAXN];
bool st[MAXN];
void add(int a,int b,int c){
e[idx]=b,w[idx]=c;
ne[idx]=h[a],h[a]=idx++;
}
int dijkstra(){
memset(dis,0x3f,sizeof(dis));
dis[1]=0;
priority_queue<pii,vector<pii>,greater<pii>> heap;
heap.push({0,1});
while(heap.size()){
auto u = heap.top();heap.pop();
int ver = u.second,distance = u.first;
if(st[ver])
continue;
st[ver]=true;
for(int i=h[ver];i!=-1;i=ne[i]){
int j=e[i];
if(dis[j]>distance+w[i]){
dis[j]=distance+w[i];
heap.push({dis[j],j});
}
}
}
if(dis[n]==0x3f3f3f3f) return -1;
return dis[n];
}
|
Bellman_Ford算法 O(n*m)
任意存边方式都可，建议结构体
1
2
3
4
5
6
| for(n次){
备份（防止用更新过的点更新其他点）
for 所有从a走到b的边，权重是w{
dis[b]=min(dis[b],dis[a]+w);
}
}
|
循环完，所有边都满足三角不等式dis[b]<=dis[a]+w;迭代k次表示经过不超过k条边的最短路的距离。如果第n次迭代仍然有边更新，根据抽屉原理，说明有负环。因此，Bellman-Ford算法可以用来找负环。
注意：如果有负权回路，最短路不一定存在
代码：
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
| #include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;
#define MAXN 10010
#define maxn 510
struct Edge{
int a,b,w;
} edge[MAXN];
int dis[MAXN],backup[MAXN];
int n,m,k;
int bellman_ford(){
memset(dis,0x3f,sizeof(dis));
dis[1]=0;
for(int i=1;i<=k;i++){
memcpy(backup,dis,sizeof(dis));
for(int j=1;j<=m;j++){
int a=edge[j].a,b=edge[j].b,w=edge[j].w;
dis[b]=min(dis[b],backup[a]+w);
}
}
if(dis[n]>0x3f3f3f3f/2) return -1;
return dis[n];
}
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=m;i++){
int a,b,w;
scanf("%d%d%d",&a,&b,&w);
edge[i].a=a,edge[i].b=b,edge[i].w=w;
}
int t=bellman_ford();
if(t==-1) puts("impossible");
else printf("%d\n",t);
return 0;
}
|
SPFA算法
步骤：
0.用邻接表存储1.队头入队，更新st数组2.BFS思路while队列不空,t<-q.front(),p.pop()3.遍历t的邻接表，更新dis[]数组，即t每一出点的最小距离；4.在每一出点判断，如果不在队列里，则加入队列；5.最后迭代完之后的判断
代码：
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
| #include<iostream>
#include<string>
#include<algorithm>
#include<string.h>
#include<queue>
#define MAXN 160010
using namespace std;
typedef pair<int,int> pii;
int n,m,idx;
int h[MAXN],e[MAXN],ne[MAXN],w[MAXN];
int dis[MAXN];
bool st[MAXN];
int spfa(){
memset(dis,0x3f,sizeof(dis));
dis[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!=-1;i=ne[i]){
int j=e[i];
if(dis[j]>dis[t]+w[i]){
dis[j]=dis[t]+w[i];
if(!st[j]){
Q.push(j);
st[j]=true;
}
}
}
}
if(dis[n]==0x3f3f3f3f) return -1;
return dis[n];
}
|
求负环：
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
| bool spfa(){
queue<int> Q;
for(int i=1;i<=n;i++){
st[i]=true;
Q.push(i);
}
while(Q.size()){
int t=Q.front();Q.pop();
st[t]=false;
for(int i=h[t];i!=-1;i=ne[i]){
int j=e[i];
if(dis[j]>dis[t]+w[i]){
dis[j]=dis[t]+w[i];
cnt[j] = cnt[t]+1;
if(cnt[j]>n) return true;
if(!st[j]){
Q.push(j);
st[j]=true;
}
}
}
}
return false;
}
|
Floyd算法 O(n^3)
1.邻接矩阵 d [ i , j ] 存图中每个点
1
2
3
4
| for(k=1~n)
for(i=1~n)
for(j=1~n)
d[i][j]=min(d[i][j],d[i][k]+d[k][j];
|
d[k,i,j]表示从i点经过1~k中间点到达j的最短距离
因此基于动态规划的状态转移方程为：
1
| d[k,i,j]=min(d[k,i,j],d[k-1,i,k]+d[k-1,k,j])
|
从i到j只经过k-1这些点，再从k到j只经过1~k-1这些点，加在一起就是从i~j经过k个点,而k-1可以压缩掉，故状态转移方程为
1
| d[i][j]=min(d[i][j],d[i][k]+d[k][j];
|
Floyd算法用来解决的问题：
1.最短路问题
2.传递闭包
3.找最小环
4.恰好经过k条边的最短路径
传递闭包
在有向图中，能间接到的点也连一条有向边
邻接矩阵的表示方式：已知g(i,j),求d(i,j)
1.初始化 d(i,j)=g(i,j)
2.对d(i,j)做一遍Floyd
1
2
3
4
5
6
| g(i,j)=存在i->j?1:0
for k:n
for i:n
for j:n
if(d(i,k)==1&&d(k,j)==1) d(i,j)=1
|
矛盾的判断方式：d(i,i)=1
能唯一确定的判断方式: i != j 必有 d(i,j) | d(j,i) == 1
顺序不唯一：处于中间阶段
恰好经过k条边的最短路径之改进Floyd
1
2
3
4
| Floyd: d[k,i,j]表示从i到j只经过1-k的最短路径
本思路： d[k,i,j]表示从i到j，恰好经过k条边的最短路径
则状态转移方程为：
d[a+b,i,j]=min(d[a,i,k]+d[b,k,j]) k=1-n
|
k指的是第a个点，此算法可以处理有负环的情况
使用倍增的思想来拼接，用logn的复杂度逼近k