By Shiina Orez

Updated:

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）：