Contents
  1. 1. 图论
    1. 1.1. Floyd:
    2. 1.2. Dijkstra:
      1. 1.2.1. 过程
    3. 1.3. SPFA(Shortest Path Faster Algorithm):

图论

图论是OI比赛中最重要的部分 。OI中除了送分题和数论题,基本都是图论的题目。

最短路是图论中一个比较核心的问题。在一个图中(有向,无向//有环,无环//有负边权,无负边权)两个点,如何找到一个花费最小的路径呢?

在高中我接触到了4个最短路算法:Floyd,Dijkstra,Bellman-Ford,SPFA
今天只打算讲除了Bellman-Ford之外的三个算法。
你都有SPFA了干嘛还要写BF

Floyd:

本算法的复杂度是算法界中首屈一指的高:O(n³)
但是,它被沿用的原因有两个:

1.对Floyd单次的调用可以获得所有的点对之间的最短路径。
2.可以处理正负边权的情况。

本算法的三个循环:
第一层循环是对中间点的穷举;
第二层循环是对起点的穷举;
第三层循环是对终点的穷举;

而确立最短路径的地过程,更像是一个动态规划:

  • 状态转移方程:map[i,j]:=min{map[i,k]+map[k,j],map[i,j]};
    其中map记录了最短路的情况

经过这个动态转移方程的描述,可以更加清楚地看到Floyd的本质。

代码:

1
2
3
4
5
6
7
8
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++){
if(d[i][k]+d[k][j]<d[i][j]){
d[i][j]=d[i][k]+d[k][j];
path[i][j]=path[i][k];
}
}

Dijkstra:

这个算法用于处理一对结点之间的问题,算法复杂度在n²。
不能处理含有负边权的情况。

dijkstra的思路其实有一些像prim算法的思路(笑
所以其实我懒得写了?

过程

我们将整个图中的点分为两个集合;
一个集合是已扩展的点集,S,一个集合是未扩展的,V。
显而易见,一开始S是空集,而V包含所有的点。

第一步,我们将起点加入S。
然后,选择S连接的点中,花费(边权)最 小的点。加入S。
然后更新这个集合所连接的所有的点的花费。
(一步步…一步步…..直到所有的点都扩展了,我们就得到了终点的最终花费)

代码;

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
64
65
66
#include<cstdio>
#include<algorithm>
#include<iostream>
#define maxn 100005
using namespace std;
struct node{
int next;
int to;
int w;
}edge[maxn];
struct Node{
int w;
bool ty;
}dis[maxn];
int n,m,q,e=0,head[maxn];
void add(int u,int v,int d){
edge[++e].next=head[u];
edge[e].to=v;
edge[e].w=d;
head[u]=e;
return ;
}
void dij(int x){
int c=n-1;
dis[x].ty=1;
for(int i=head[x];i!=0;i=edge[i].next)
dis[edge[i].to].w=edge[i].w;
while(c>0){
int min=900000000,p;
for(int i=1;i<=n;i++){
if(dis[i].ty==0&&dis[i].w!=0&&dis[i].w<min){
p=i;
min=dis[i].w;
}
}
for(int i=head[p];i!=0;i=edge[i].next){
if(dis[edge[i].to].ty!=1){
if(dis[edge[i].to].w==0||dis[edge[i].to].w>dis[i].w+edge[i].w)
dis[edge[i].to].w=dis[p].w+edge[i].w;
}
}
dis[p].ty=1;
c--;
}
return ;
}
int main(){
int u,v,d,x,y;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&u,&v,&d);
add(u,v,d);
add(v,u,d);
}
scanf("%d",&q);
for(int i=1;i<=q;i++){
scanf("%d%d",&x,&y);
dij(x);
printf("%d\n",dis[y].w);
for(int j=1;j<=n;j++){
dis[j].w=0;
dis[j].ty=0;
}
}
return 0;
}

SPFA(Shortest Path Faster Algorithm):

SPFA的另一个作用:判定图中是否含有负数环23333

用数组d记录每个结点的最短路径估计值,而且用邻接表来存储图G。
我们采取的方法是动态逼近法

设立一个先进先出的队列用来保存待优化的结点,优化时每次取出队首结点u,并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作,如果v点的最短路径估计值有所调整,且v点不在当前的队列中,就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作,直至队列空为止。

如果一个点进入队列达到n次,则表明图中存在负环,没有最短路径。

复杂度:
期望时间复杂度:O(me), 其中m为所有顶点进队的平均次数,可以证明m一般小于等于2n:

“算法编程后实际运算情况表明m一般没有超过2n.事实上顶点入队次数m是一个不容易事先分析出来的数,但它确是一个随图的不同而略有不同的常数.所谓常数,就是与e无关,与n也无关,仅与边的权值分布有关.一旦图确定,权值确定,原点确定,m就是一个确定的常数.所以SPFA算法复杂度为O(e).证毕."(SPFA的论文)

伪代码;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ProcedureSPFA;
Begin
initialize-single-source(G,s);
initialize-queue(Q);
enqueue(Q,s);
while not empty(Q) do begin
u:=dequeue(Q);
for each v∈adj[u] do begin
tmp:=d[v];
relax(u,v);
if(tmp<>d[v])and(not v in Q)then enqueue(Q,v);
end;
end;
End;

求最短路不要拘束于这四种算法,很多算法会有出其不意的效果。
比如我们可以把一个图拽起来,变成一棵树。
然后最短路就是求LCA了233333

求出LCA时,记录逆dfs序列,直接写出路径。

SPFA给我们做了一个好榜样,我们要自己去琢磨新的算法,新的思路。

最后还是祝各位OIer武运昌隆!

这里写图片描述

Contents
  1. 1. 图论
    1. 1.1. Floyd:
    2. 1.2. Dijkstra:
      1. 1.2.1. 过程
    3. 1.3. SPFA(Shortest Path Faster Algorithm):