最短路径专题（Dijkstra、Floyd、Bellman-Ford即优化）

[TOC]

Flody Dijkstra 堆优化的Dijkstra Bellman-Ford 队列优化的Bellman-Ford
时间复杂度 O($N^3$) O($N^2$) O((M+N)logN) O(MN) 最坏O(MN)
适用情况 稠密图
和顶点关系密切		 稠密图
和定点关系密切		 稠密图
和定点关系密切		 稀疏图
和边关系密切		 稀疏图
和边关系密切
负权 可以解决负权 不能解决负权 不能解决负权 可以解决负权 可以解决负权

五行代码的Flody

看到$N^3$的时间复杂度不要一脸瞧不起，人家算的可是任意两点间的最短距离。
算法分析
edge[i][j]首先表示i号顶点到j号顶点的路程，我们希望最终它存储的是i到j的最短距离
如果只允许经过1号点，求i到j的最短距离，那么只需i，j都遍历1~m次

1
2
3
4
for(int i = 1; i <=m; ++i)
    for(int j = 1; j <=m; ++j)
        if(edge[i][j] > edge[i][1]+edge[1][j])
            edge[i][j] = edge[i][1]+edge[1][j];

如果只把1号换成2号点，再执行一遍上面的程序，得到的就是只允许经过1号、2号两个顶点i到j的最短距离；
那么执行m次，就得到i到j的最短距离了？
假设i到j的最短路经为i、d、k、m、j；
Flody用到了动态规划的思想：

  • 重复子问题：求i到j的最短路需要知道i到m的最短路、求i到m的最短路需要i到k的最短路……
  • 最优子结构：最短路（i,j）=最短路（i，m）+edge[m,j]
    于是我们可以用一段话概括Flody的算法思想了。

算法思想
最开始只允许经过1号顶点进行中转，接下来允许经过1号和2号顶点进行中转……
允许经过1~n号所有顶点进行中转，求得任意两点间的最短距离。
Flody核心代码：

1
2
3
4
5
for(k=1; k<=m; k++)
		for(i=1; i<=m; i++)
			for(j=1; j<=m; j++)
				if(edge[i][j]>edge[i][k]+edge[k][j])
					edge[i][j]=edge[i][k]+edge[k][j];

——————————————————————代码如下———————————————————————————

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
//Floyd
#include <cstdio>
#include <iostream>
#define M 100

using namespace std;

const int INF=0x3f3f3f3f;
int main()
{
	int i,k,j,m,n,s,e,value;
	int edge[M][M];
	cin>>m>>n;  //点数m，边数n
	for(i=1; i<=m; i++)
	{
		for(j=1; j<=m; j++)
		{
			if(i==j)
				edge[i][j]=0;
			else
				edge[i][j]=INF;
		}
	}
	for(i=0; i<n; i++)
	{
		cin>>s>>e>>value;
		edge[s][e]=value;
	}
	for(k=1; k<=m; k++)
		for(i=1; i<=m; i++)
			for(j=1; j<=m; j++)
			{
				if(edge[i][j]>edge[i][k]+edge[k][j])
					edge[i][j]=edge[i][k]+edge[k][j];
			}
	for(i=1; i<=m; i++)
	{
		for(j=1; j<=m; j++)
		{
			if(edge[i][j]<0)
				printf("负圈\n");
			else
				printf("%d ",edge[i][j]);
		}
		printf("\n");
	}
	return 0;
}

Dijkstra

Dijkstra求解的是单源最短路径问题
算法分析
使用dis[]数组表示源点到其余各点的路程，我们希望最终存储源点到各个点的最短路径；
Dijkstra同样利用了最优子结构这一要点：
即假设i到j的最短路经为i、d、k、m、j；
那么dis[j] = dis[m] + edge[m][j];
于是首先找距离i最近的点，假设记为t，坚信i到t的最短路径已经得到了（dis[t]不用更新了）；
标记一下count = t，以t为顶点开始对其他点进行松弛:

1
2
3
4
5
for(k = 1; k <= m; k++)	//开始松弛 
{
	if(edge[count][k] < INF && dis[k] > dis[count]+edge[count][k])
		dis[k] = dis[count] + edge[count][k];
}

dis[] 因为dis[t]更新了一遍，接着再找距离i最近的点，再松弛……
问：为何如此坚信一旦找到距离i最近的点t，dis[t]就是i到t的最短路径了？
答：假设此刻的dis[t]不是最短的，还有另一条路可以到t且最短，那么找寻距离i最近的点时根本不会是t！
由此可以看到Dijksta是基于BFS，松弛的操作有动态规划和贪心的思想，用一段话概括Dijkstra的算法思想。

算法思想

  1. 每次寻找未访问的、离源点最近的一个顶点，标记为已访问，然后以该顶点为中心对其他点进行松弛
  2. 重复步骤1，直到所有点均访问完，最终得到源点到其余所有点的最短距离

——————————————————————————核心代码——————————————————————————————

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
//Difkstra
#include <cstdio>
#include <iostream>
#define M 100
using namespace std;
int m, n;
int edge[M][M], dis[M], visit[M];
const int INF=0x3f3f3f3f;
void Dijkstra(int st)//源点st
{
	for(int i = 1; i <= m; i++)
		dis[i] = edge[st][i];
	for(int i = 1; i <= m; i++)
		visit[i] = 0;
	visit[st] = 1;	//源点到自身的最短距离为0 
	for(int i = 1; i < m; i++)
	{
		int count, min = INF;
		for(int j = 1; j <= m; j++)	//找dis[]中未访问过的、离源点最近的点
		{
			if(visit[j] == 0 && dis[j] < min)
			{
				min = dis[j];
				count = j;	
			}
		}
		visit[count] = 1;	//从该顶点出发更新相邻顶点的最短距离 
		for(int k = 1; k <= m; k++)	//开始松弛 
		{
			if(edge[count][k] < INF && dis[k] > dis[count]+edge[count][k])
				dis[k] = dis[count] + edge[count][k];
		}
		for(int k = 1; k <= m; k++)
			printf("%d ",dis[k]);
		printf("\n");
	}
}

堆优化的Dijkstra

算法思想
堆优化的Dijkstra就是每次找dis[]中最小值（未访问过的）进行的优化

同时这里使用了C++的vector实现了邻接表，priority_queue实现了堆
—————————————————————————代码如下—————————————————————————————

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
//Difkstra优化
//vector+优先队列 
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#define M 100
using namespace std;

typedef struct{
	int point, weight;
}Edge;
typedef pair<int, int> Pair;	//first是最短距离,second是顶点编号 

const int Max_m=1001;
const int INF=0x3f3f3f3f;
vector<Edge> G[Max_m];
int dis[Max_m];

void Dijkstra(int st)
{								//指定greater参数,堆按从小到大顺序取出 
	priority_queue<Pair, vector<Pair>, greater<Pair> > que;
	memset(dis, 0x3f, sizeof(dis));
	dis[st]=0;
	que.push(Pair(0,st));
	
	while(!que.empty())
	{
		Pair p = que.top();
		que.pop();
		int v = p.second;		//顶点编号 
		if(dis[v] < p.first)
			continue;
		for(int i = 0; i < G[v].size(); i++)
		{
			Edge e = G[v][i];
			if(dis[e.point] > dis[v] + e.weight)
			{
				dis[e.point] = dis[v] + e.weight;
				que.push(Pair(dis[e.point], e.point));
			}	
				
		}
	}
	
}
int main()
{
	int i,k,j,m,n,count,min,s,e,value;
	cin>>m>>n;
	for(i=1; i<=n; i++)
	{
		Edge g;
		cin>>s>>e>>value;
		g.point=e;
		g.weight=value;
		G[s].push_back(g);
	}
	Dijkstra(1);//此刻求解的最短路是将1号作为源点
	for(int i=1; i<=m; i++)
		cout<<dis[i]<<" ";
	cout<<endl;
	return 0;
}

4行代码的Bellman-Ford

以上的算法使用于稠密图，Bellman-Ford适用于边密切的图求解最短路径；
于是不再依据点来存储边，而是依据边的个数N来存储。

1
2
3
4
5
struct edge
{
	int s,e,value;//即edge[s][e] = value;
};
edge E[N];

算法分析
和Dijkstra一样使用dis[]存放最短距离，不同的是，Dijkstra是逐个点的确定了最短路
Bellman-Ford注重于n条边的变化

1
2
3
for(i=1; i<=n; i++)
	if(dis[E[i].e]>dis[E[i].s]+E[i].value)
		dis[E[i].e]=dis[E[i].s]+E[i].value;

显然这并没有专注于某个顶点，而是对所有边进行了一次松弛，经过这一轮的松弛，更新的dis[]表示：
只经过一条边，从源点到任意顶点的最短路径长；
按照这个思路，求源点到任意顶点的最短路只需松弛m-1次即可！（两点间最多经过m-1条边）
于是用一句话概括Bellman-Ford的算法思想。
算法思想
对所有边进行m-1次松弛操作
核心代码：

1
2
3
4
for(k=1; k<=m-1; k++)
	for(i=1; i<=n; i++)
		if(dis[E[i].e]>dis[E[i].s]+E[i].value)
			dis[E[i].e]=dis[E[i].s]+E[i].value;

加了判断负环的操作，如果第m次还在更新，说明有负环
—————————————————————————代码如下———————————————————————————

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
//Bellman-Ford
#include <cstdio>
#include <iostream>
#define M 100
#define N 100
using namespace std;

const int INF=0x3f3f3f;
struct edge
{
	int s,e,value;
};
edge E[N];
int main()
{
	int i,j,k,m,n;
	int dis[M];
	cin>>m>>n;
	for(i=1; i<=n; i++)
		cin>>E[i].s>>E[i].e>>E[i].value;
	for(i=1; i<=m; i++)
		dis[i]=INF;
	dis[1]=0;//这里就把1号作为源点
	for(k=1; k<=m; k++)
		for(i=1; i<=n; i++)
			if(dis[E[i].e]>dis[E[i].s]+E[i].value)
			{
				dis[E[i].e]=dis[E[i].s]+E[i].value;
				if(k==m)
				{
					printf("负圈\n");
				}
			}
    for(j=1; j<=m; j++)
			printf("%d ",dis[j]);
	printf("\n");
	return 0;
}

队列优化的Bellman-Ford

队列优化的Bellman-Ford相比堆优化的Dijkstra就不那么好理解了