浅谈图的最短路

图的最短路

图的最短路算法主要分为以下几种

Dijkstra(only 正权图)

Bellman-Ford

SPFA(Bellman-Ford的改进，不能有负权环)

Floyd(n^3，多源点最短路)

这里主要介绍Dijkstra,SPFA和Floyd

代码的补充说明

名称	类型	表
a	vector	邻近点数组
b	int[]	标记数组
d	int[]	距离数组
edge	pair	具体看代码的注释

for(auto i:a){}

C++11提供的新的遍历数组和容器的方法

auto

C++11引入的，让系统自己判断此处auto替代的类型

Dijkstra(仅用于正权图) 无优化

设s为起点,数组d为各点到s的距离，初始化为114514

其法:

1. 松弛s的邻近点

for(int i=1;i

2. 找到d中最小的且没有标记过的，让它作为新的起点ss

3. 松弛ss的邻近点(比较 d[邻近点] d[ss]+(ss到这个邻近点的权值))

}

此时d数组保存的值就是s到个点的最短路

a是存邻近点的vector
.first表到的点，.second表边权
void djstl(const int &n, int f)
{
	int d[n + 1], m, mn, s = f;
	bool b[n + 1]{0};//标记
	for (int i = 0; i <= n; i++)
		d[i] = 114514;//初始化为无限大
	d[f] = 0;
	b[s] = 1;
	for (auto i : a[s])//松弛s邻近点
		if (i.second < d[i.first])
			d[i.first] = i.second;
	for (auto i = 1; i < n; i++)
	{
		mn = 114514;//初始化
		for (auto j = 1; j <= n; j++)
			if (!b[j] && mn > d[j])//找最小的
				mn = d[j], s = j;
		for (auto j : a[s])//松弛邻近点
			if (d[j.first] > d[s] + j.second)//如果能松弛
				d[j.first] = d[s] + j.second;//松弛
		b[s] = 1;//标记
	}
	for (auto i = 1; i <= n; i++)
		cout << d[i] << endl;
	return;
}

堆优化

其法:

1. 松弛s的邻近点,拖堆里

for(int i=1;i

2. ss=堆顶 去掉了欸个找的流程

3. 松弛ss的邻近点(比较 d[邻近点] d[ss]+(ss到这个邻近点的权值))，
   把d[邻近点]拖推里

}

此时d数组保存的值就是s到个点的最短路

以下是堆的代码

typedef pair<int, int> edge;
vector<edge> a[501];
//这里的.first是到的点，.second是权值
bool operator>(edge a, edge b)
{
	return a.second > b.second;
}//重载>用于堆
void djstl(const int &n, int f)
{
	priority_queue<edge, vector<edge>, greater<edge>> aa;//创建堆aa
	//这里aa的.first是点，  .second是  距离[*.first]
	int d[n + 1]{0}, s = f;
	for (int i = 1; i <= n; i++)
		d[i] = 114514;//初始化为无限大
	for (auto i : a[s])//松弛s的邻近点
	{
		if (i.second < d[i.first])
		{
			d[i.first] = i.second;//松弛s邻近点,
			aa.push({i.first, d[i.first]});//入堆
		}
	}
	for (auto i = 1; i < n; i++)
	{
		s = aa.top().first;//取堆顶，将堆顶作为起点
		aa.pop();//d出堆
		for (auto j : a[s])//遍历起点的邻近点
		{
			if (d[j.first] > d[s] + j.second)//松弛s邻近点
			{
				d[j.first] = d[s] + j.second;//松弛
				aa.push({j.first, d[j.first]});//入堆
			}
		}
	}
	for (auto i = 1; i <= n; i++)
		cout << d[i] << endl;
	return;
}

SPFA SPFA用宽搜实现

其法:

int setp=0;
while(队列不为空)
{
	setp++;
	if(step>总边数)
	{
		说明这题有负权环;
		输出(“无解”);
		return 0;
	}
	for(遍历队首邻近点)
	{
		if(能够松弛d[邻近点]>权+d[队首])
		{
			if(不在队列里)
			{
				松弛;
				将邻近点入队;
			}
		}
	}
	取消标记队首;
	d出队首;
}

code如下

//这里是求1到n的

void spfa()
{
	array<int, N> d;
	array<int, N> b;
	queue<int> u;//队列
	for (auto &i : d)
		i = 114514;//初始化
	for (auto &i : b)
		i = false;//初始化
	u.push(1);//初始化
	b[1] = 1;//初始化
	d[1] = 0;//初始化
	while (!u.empty())//如果队列不空
	{
		step++;//记录步数
		if (step > m)//有负权环
		{
			printf("No Solution");
			exit(0);
		}
		int f = u.front();//取队首
		for (auto i : a[f])//松弛队首的邻近点
		{
			if (d[i.first] > i.second + d[f])//如果能松弛
			{
				d[i.first] = i.second + d[f];//松弛
				if (!b[i.first])//不在队列里
				{
					b[i.first] = true;//标记
					u.push(i.first);//入队
				}
			}
		}
		b[f] = 0;//取消标记
		u.pop();//出队
	}
	cout << d[n];
}

Floyd

点i到j的路有两种:i到j，i到中介k再到j
所以，可以用DP解决
d[i][j]表i到j的距离

先初始化d，全部为最大值
把所有点的所有邻近点的权值放入f中
(连上能直接连上的点)
然后:

for (int k = 1; k <= n; k++)//枚举中介k
	for (int i = 1; i <= n; i++)//枚举i
		for (int j = 1; j <= n; j++)//枚举j
			if (i != k && i != j && j != k)
				if (d[i][k] + d[k][j] < d[i][j])//能被松弛
					d[i][j] = d[i][k] + d[k][j];
cout<<d[from][to];