首页 > 编程语言 >【图论】（五）最短路径算法（D / BF / SPFA / F / A*）

【图论】（五）最短路径算法（D / BF / SPFA / F / A*）

时间：2024-10-23 19:22:02浏览次数：3  
标签：图论 cur int 源点 BF SPFA minDist grid 节点

最短路径算法（D / BF / SPFA / F / A*）

1. 最短路径之dijkstra（D算法）

最短路径问题： 从一个点 出发，到终点走过的最短路径之和的问题

输入描述： 第一行包含两个正整数，第一个正整数 N 表示一共有 N 个节点，第二个正整数 M 表示有 M 条边。

接下来为 M 行，每行包括三个整数，S、E 和 V，代表了从 S 节点可以单向直达 E 节点，并且要花费 V 单位的时间。

输出描述： 输出一个整数，代表小明从起点到终点所花费的最小时间。

输入示例：

7 9
1 2 1
1 3 4
2 3 2
2 4 5
3 4 2
4 5 3
2 6 4
5 7 4
6 7 9

输出示例： 12

提示信息：

能够到达的情况： 如下图所示，起始节点为 1 号节点，终点车站为 7 号节点，绿色路线为最短的路线，路线总长度为 12，则输出 12。

不能到达的情况： 如下图所示，当从起始车站不能到达终点车站时，则输出 -1。

思路

dijkstra算法： 在有权图（权值非负数）中求从起点到其他节点的最短路径算法。

需要注意两点：

  • dijkstra 算法可以同时求 起点到所有节点的最短路径
  • 权值不能为负数

dijkstra 算法 和之前的prim算法思路非常接近，建议先复习复习prim算法再复习D算法。

dijkstra 算法 同样是贪心的思路，不断寻找距离 源点最近的没有访问过的节点。

dijkstra三部曲：

  • 第一步，选源点到哪个节点近且该节点未被访问过
  • 第二步，该最近节点被标记访问过
  • 第三步，更新非访问节点到源点的距离（即更新minDist数组）

在dijkstra算法中，同样有一个数组很重要，起名为：minDist。

minDist数组 用来记录 每一个节点距离源点的最小距离。

minDist数组 用来记录 每一个节点距离源点的最小距离。

模拟过程

☆ 状态0 初始化

  • minDist数组的含义：记录所有节点到源点的最短路径，那么初始化的时候就应该初始为最大值，这样才能在后续出现最短路径的时候及时更新。

  • 节点0 不做处理，统一从下标1 开始计算，初始化 minDist[1] = 0，到自身的距离为0，所有节点都没有被访问过，所以 visited 数组都为 false

☆ 状态1 模拟过程

1. 选源点到哪个节点近且该节点未被访问过： 源点距离源点最近，距离为0，且未被访问。

2. 该最近节点被标记访问过： 标记源点访问过

3. 更新非访问节点到源点的距离（即更新minDist数组） ， 如图：

 
更新 minDist数组，即：源点（节点1） 到 节点2 和 节点3的距离。

  • 源点到节点2的最短距离为1，小于原minDist[2]的数值max，更新minDist[2] = 1
  • 源点到节点3的最短距离为4，小于原minDist[3]的数值max，更新minDist[3] = 4

minDist[2] 的含义，它表示源点到节点2的最短距离，那么目前我们得到了 源点到节点2的最短距离为1，小于默认值max，所以更新。 minDist[3]的更新同理。

状态2 再熟悉过程

1. 选源点到哪个节点近且该节点未被访问过： 未访问过的节点中，源点到节点2距离最近，选节点2

2. 该最近节点被标记访问过： 节点2被标记访问过

3. 更新非访问节点到源点的距离（即更新minDist数组） ， 如图：

 
更新 minDist数组，即：源点（节点1） 到 节点6 、 节点3 和 节点4的距离

为什么更新这些节点呢？ 怎么不更新其他节点呢？

因为 源点（节点1）通过 已经计算过的节点（节点2） 可以链接到的节点 有 节点3，节点4和节点6.

更新 minDist数组：

  • 源点到节点6的最短距离为5，小于原minDist[6]的数值max，更新minDist[6] = 5
  • 源点到节点3的最短距离为3，小于原minDist[3]的数值4，更新minDist[3] = 3
  • 源点到节点4的最短距离为6，小于原minDist[4]的数值max，更新minDist[4] = 6

程序实现

☆ 状态3 引入程序

1. 选源点到哪个节点近且该节点未被访问过： 如何查找哪个源点到最近的未遍历过的节点。
（1）遍历所有节点，判断是否被访问过：visited[j] == false
（2）计算源点到该未被访问过节点的距离：minDist[j]
（3）就算遍历过程中每次计算距离的最小值，保存节点与到节点的距离

 
伪代码实现：

int minDis = INT_MAX;		// 记录节点到源点的最小值
int cur;					// 记录距离最小值对应的节点
for(int j = 1; j <= n; j++)	// 遍历所有节点
{
	//找到一个未访问(不在最短路径中)的节点
	//并且该节点是剩下节点中距离源点更近
	if(visited[j] == false && minDist[j] < minDis) 
	{
		cur = j;				//记录节点
		minDis = minDist[j];	//记录距离
	}
}

程序结束：

cur = 3			//记录节点 3
minDis = 3;		//记录距离本轮到源点最近的距离为 3

2. 该最近节点被标记访问过： 标记找到的节点3，即

visited[cur] = true

 

3. 更新非访问节点到源点的距离（即更新minDist数组） ，

  • 因为之前的minDist是各个节点通过已存在的路径走到节点1的距离，例如 mindDist[4] = 6，是节点1 -> 节点2 -> 节点6
  • 而上述加入了节点3，mindDist[6] 存在一条更短距离的路径，即节点1 -> 节点2 -> 节点3 -> 节点4，路径为5，小于之前的mindDist[4]（6）
  • 为什么会出现这种情况呢？因为加入了节点3，多了一条 节点3 -> 节点4的路径，这这条路径在不加节点3之前是不存在的。
  • 因此再加入cur节点后，需要更新未访问过的节点到源点的距离，即更新未访问节点的 minDist数组
  • 如何更新？ 何如产生就如何更新，将加入新节点的minDist[cur] + 周围的边，与原有的minDist[j] 比较，取最小值

 
更新 minDist数组：

  • 源点到节点6的最短距离为5，小于原minDist[6]的数值max，更新minDist[6] = 5
  • 源点到节点3的最短距离为3，小于原minDist[3]的数值4，更新minDist[3] = 3
  • 源点到节点4的最短距离为6，小于原minDist[4]的数值max，更新minDist[4] = 6
// 3、更新非访问节点到源点的距离（即更新minDist数组）
// 遍历cur邻接的节点(cur的邻边)
for(int j = 1; j <= n; j++)
{
	// !visited[j] 未访问过的节点
	// cur邻边有值，即是与cur直连的
	// minDist[cur] + grid[cur][j] < minDist[j] 存在比之前更短的路径 更新mindDist[j]
	if(!visited[j] && grid[cur][j] != INT_MAX && minDist[cur] + grid[cur][j] < minDist[j])
	{
		minDist[j] = minDist[cur] + grid[cur][j];
	}
}

完整程序实现：

#include <iostream>
#include <vector>
#include <climits>
using  namespace std;

int main()
{
	int n, m;	// n个节点 m条边
	cin >> n >> m;
	
	int s, e, v;
	vector<vector<int>> grid(n + 1, vector<int>(n + 1, INT_MAX));
	while(m--)
	{
		cin >> s >> e >> v;
		grid[s][e] = v;
	}
	
	//标记起点和终点
	int start = 1;
	int end = n;
	
	// 标记节点1到每个节点的最短距离
	vector<int> minDist(n+1, INT_MAX);
	// 标记每个节点是否被访问过
	vector<bool> visited(n+1,false);
	minDist[start] = 0;
	
	for(int i = 0; i <= n; i++)
	{
		int minDis = INT_MAX;		// 记录本轮循环中距离最近的点的距离
		int cur = 1;				// 记录本轮循环中距离最近的点
		
		// 1、选距离源点最近且未访问过的节点
		// 判断是否加入路径的要求
		//1. 该节点没有被访问过
		//2. 该节点距离当前节点距离最短
		for(int j = 1; j <= n; j++)
		{
			if(!visited[j] && minDist[j] < minDis)
			{
				minDis = minDist[j];
				cur = j;
			}
		}
		
		// 2、标记该节点已被访问
		visited[cur] = true;
		
		// 3、更新非访问节点到源点的距离（即更新minDist数组）
		// 遍历cur邻接的节点(cur的邻边)
		for(int j = 1; j <= n; j++)
		{
			// !visited[j] 未访问过的节点
			// cur邻边有值，即是与cur直连的
			// minDist[cur] + grid[cur][j] < minDist[j] 存在比之前更短的路径 更新mindDist[j]
			if(!visited[j] && grid[cur][j] != INT_MAX && minDist[cur] + grid[cur][j] < minDist[j])
			{
				minDist[j] = minDist[cur] + grid[cur][j];
			}
		}
	}
	
	if(minDist[end] == INT_MAX)
		cout << "-1" << endl;
	else
		cout << minDist[end] << endl;
}

拓展

1. 如何记录边

  记录边，通prim算法一样，只需要定义一个存放边的容器，在最后更新minDist数组的时候，存在更短的路径时候将对应的边加入即可。

初始化：

//加上初始化
vector<int> parent(n + 1, -1);

发现新的更短路径边时，加入对应的边：

for(int j = 1; j <= n; j++)
{
	if(!visited[j] && grid[cur][j] != INT_MAX && minDist[cur] + grid[cur][j] < minDist[j])
	{
		minDist[j] = minDist[cur] + grid[cur][j];
		parent[j] = cur;		 // 记录边
	}
}
2. 权值出现出现负数

 
节点1 到 节点5 的最短路径： 应该是 节点1 -> 节点2 -> 节点3 -> 节点4 -> 节点5

初始化及状态1：

状态2化及状态3：

状态4化及状态5：

 
至此dijkstra的模拟过程就结束了，根据最后的minDist数组，我们求 节点1 到 节点5 的最短路径的权值总和为 3，路径： 节点1 -> 节点3 -> 节点4 -> 节点5

对于求解带有负权值的最短路问题，需要使用后续的 Bellman-Ford 算法

为什么D算法不能有负边？

本质： dijkstra是基于贪心策略，每次都找一个距源点最近的点，然后将该距离定为这个点到源点的最短路径；但如果存在负权边，那就有可能先通过并不是距源点最近的一个次优点，再通过这个负权边，使得路径之和更小，这样就出现了错误。

3. dijkstra与prim算法的区别

P算法和K算法及其相似，只有在第三部更新数组的时候有差异：

  • 因为prim是求 非访问节点到最小生成树的最小距离，而 dijkstra是求 非访问节点到源点的最小距离。

prim 更新 minDist数组的写法：

for (int j = 1; j <= v; j++) {
    if (!isInTree[j] && grid[cur][j] < minDist[j]) {
        minDist[j] = grid[cur][j];
    }
}

因为 minDist表示 节点到最小生成树的最小距离，所以 新节点cur的加入，只需要 使用 grid[cur][j] ，grid[cur][j] 就表示 cur 加入生成树后，生成树到 节点j 的距离。

dijkstra 更新 minDist数组的写法：

for (int v = 1; v <= n; v++) {
    if (!visited[v] && grid[cur][v] != INT_MAX && minDist[cur] + grid[cur][v] < minDist[v]) {
        minDist[v] = minDist[cur] + grid[cur][v];
    }
}

因为 minDist表示 节点到源点的最小距离，所以 新节点 cur 的加入，需要使用 源点到cur的距离 （minDist[cur]） + cur 到 节点 v 的距离 （grid[cur][v]），才是 源点到节点v的距离。

prim算法 可以有负权值吗？

prim算法只需要将节点以最小权值和链接在一起，不涉及到单一路径，因此当然可以存在负权值的边。

2. dijkstra算法堆优化

dijkstra算法三部曲：

  • 第一步，选源点到哪个节点近且该节点未被访问过
  • 第二步，该最近节点被标记访问过
  • 第三步，更新非访问节点到源点的距离（即更新minDist数组）

在上述的dijkstra基础坂中，该解法的时间复杂度为 O ( n 2 ) O(n^2) O(n2)，可以看出时间复杂度 只和 n （节点数量）有关系，如果n很大的话，我们可以换一个角度来优先性能，即：从边的数量出发。

思路

（一）对于从边的角度出发，图的存储一定是采用邻接表法：

  • 邻接表 使用 数组 + 链表的方式来表示。 邻接表是从边的数量来表示图，有多少边 才会申请对应大小的链表。

 
（二）当从边 的角度出发， 在处理 三部曲里的第一步（选源点到哪个节点近且该节点未被访问过）的时候 ，我们可以不用去遍历所有节点了，这也是堆优化降低时间复杂度的地方。

  • 而且 直接把 边（带权值）加入到 小顶堆（利用堆来自动排序），那么每次我们从 堆顶里 取出 边 自然就是 距离源点最近的节点所在的边。

  • 这样我们就不需要两层for循环来寻找最近的节点了。

程序实现

（一）图的存储

  • 邻接表用 数组+链表 来表示，并且通过结构体来封装一条边，带权值的边都是这么定义的
    //邻接表的定义 
// 定义一个结构体来表示带权重的边
struct Edge {
	int to; 	 	// 链接的节点
	int val; 		// 边的权重
	
	Edge(int t, int w):to(t),val(w){}	// 构造函数
};

//存储边
vector<list<Edge>> grid(n+1);
int p1,p2,val;
while(m--)
{
	cin >> p1 >> p2 >> val;
	grid[p1].push_back(Edge(p2,val));
}

（二）堆优化细节

  • 通过优先级队列，即通过堆来对边进行排序，达到直接选择距离源点最近节点

  • 首先需要对优先级队列内的数据进行排序，那么我们关心的是需要该队列中需要存放哪些数据

    • 需要存放节点号，即获取是哪个节点
    • 存放源点到该节点的距离，因为这是排序的关键词

  • 这里对优先级队列并不熟悉，直接使用gpt模块产生的代码进行理解学习，如图

  • 程序实现

    //自定义比较器类   小顶堆 
class Mycomparison{
public:
	bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs){
		// 这里是根据第二个整数排序  
		return lhs.second > rhs.second;		// 较小的 second 应该有较高的优先级  
	}
};

// 优先队列中存放 pair<节点编号，源点到该节点的权值> 
priority_queue<pair<int, int>, vector<pair<int, int>>,Mycomparison> que;

//说明：
//priority_queue: 这是一个用于存储优先级元素的数据结构，通常是最大堆或最小堆
//默认情况下，priority_queue 是一个最大堆，即队列中最大的元素具有最高优先级
//pair<int, int>: 这指定了优先队列中存储的元素类型为 pair<int, int>，即一对整数
//vector<pair<int, int>>: 这表示优先队列将使用一个 vector 作为底层容器来存储元素。
//mycomparison: 这是一个自定义的比较器，用于定义优先队列中元素的优先级。

  • 所以三部曲中的第一步，我们不用 for循环去遍历，直接取堆顶元素：

    // pair<节点编号，源点到该节点的权值>
pair<int, int> cur = pq.top(); pq.pop();

  • 第二步（该最近节点被标记访问过） 这个就是将 节点做访问标记，和 朴素dijkstra 一样 ，代码如下：

    // 2. 第二步，该最近节点被标记访问过
visited[cur.first] = true;

  • 第三步（更新非访问节点到源点的距离），这里的思路 也是 和朴素dijkstra一样的。

    • 需要理解透彻 dijkstra 的思路
    • 理解 邻接表的表达方式
    // 第三步，更新非访问节点到源点的距离（即更新minDist数组）
// 遍历 cur指向的节点，cur指向的节点为 edge
for(Edge edge : grid[cur.first]){		
	// cur指向的节点edge.to，这条边的权值为 edge.val
	if(!visited[edge.to] && minDist[cur.first] + edge.val < minDist[edge.to]){
		minDist[edge.to] = minDist[cur.first] + edge.val;		//更新下个节点的minDist
		que.push(pair<int, int>(edge.to, minDist[edge.to]));	// 下个节点加入优先级队列
	}
}

完整程序实现：

#include <iostream>
#include <vector>
#include <climits>
#include <list>
#include <queue>

using  namespace std;

//邻接表的定义 
// 定义一个结构体来表示带权重的边
struct Edge {
	int to; 	 	// 链接的节点
	int val; 		// 边的权重
	
	Edge(int t, int w):to(t),val(w){}	// 构造函数
};

//自定义比较器类   小顶堆 
class Mycomparison{
public:
	bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs){
		// 这里是根据第二个整数排序  
		return lhs.second > rhs.second;		// 较小的 second 应该有较高的优先级  
	}
};

// 优先队列中存放 pair<节点编号，源点到该节点的权值> 
priority_queue<pair<int, int>, vector<pair<int, int>>,Mycomparison> que;

//说明：
//priority_queue: 这是一个用于存储优先级元素的数据结构，通常是最大堆或最小堆
//默认情况下，priority_queue 是一个最大堆，即队列中最大的元素具有最高优先级
//pair<int, int>: 这指定了优先队列中存储的元素类型为 pair<int, int>，即一对整数
//vector<pair<int, int>>: 这表示优先队列将使用一个 vector 作为底层容器来存储元素。
//mycomparison: 这是一个自定义的比较器，用于定义优先队列中元素的优先级。

int main()
{
	int n, m;
	cin >> n >> m;
	
	vector<list<Edge>> grid(n+1);
	int p1,p2,val;
	while(m--)
	{
		cin >> p1 >> p2 >> val;
		grid[p1].push_back(Edge(p2,val));
	}
	
	int start = 1;		// 起点
	int end = n;		// 终点
	
	// 存储从源点到每个节点的最短距离
	vector<int> minDist(n+1, INT_MAX);	
	minDist[start] = 0;				// 起始点到自身的距离为0
	
	// 记录每个节点的遍历情况
	vector<bool> visited(n+1,false);		
	
	// 优先队列中存放 pair<节点编号，源点到该节点的权值> 
	priority_queue<pair<int, int>, vector<pair<int, int>>,Mycomparison> que;
	// 初始化队列，源点到源点的距离为0，所以初始为0
	que.push(pair<int, int>(start, 0));
	
	// 遍历所有节点，第一层for循环 
	while(!que.empty()){
		/// 1. 第一步，选源点到哪个节点近且该节点未被访问过 （通过优先级队列来实现）
		// <节点， 源点到该节点的距离>
		pair<int, int> cur = que.top(); 
			que.pop();
		
		// 第二步（该最近节点被标记访问过） 
		//这个就是将 节点做访问标记，和 基础D算法 一样
		visited[cur.first] = true;  
		
		// 第三步，更新非访问节点到源点的距离（即更新minDist数组）
		// 遍历 cur指向的节点，cur指向的节点为 edge
		for(Edge edge : grid[cur.first]){		
			// cur指向的节点edge.to，这条边的权值为 edge.val
			if(!visited[edge.to] && minDist[cur.first] + edge.val < minDist[edge.to]){
				minDist[edge.to] = minDist[cur.first] + edge.val;		//更新下个节点的minDist
				que.push(pair<int, int>(edge.to, minDist[edge.to]));	// 下个节点加入优先级队列
			}
		}
	}	

	
	if (minDist[end] == INT_MAX) 
		cout << -1 << endl; 			// 不能到达终点
	else 
		cout << minDist[end] << endl; 	// 到达终点最短路径
}

拓展：

  • 堆优化需要熟悉邻接表的表达方式及其边遍历

  • 需要熟悉dijkstra的实现思路

  • 该方法适合的是稀疏图，即边比较少的图

3. Bellman_ford 算法（BF算法）

 
BF算法也是计算最短路径的常见算法，相比之前的D算法，BF算法可以计算存在负权值边的图。

最短路径问题： 从一个点 出发，到终点走过的最短路径之和的问题

输入描述： 第一行包含两个正整数，第一个正整数 N 表示一共有 N 个节点，第二个正整数 M 表示有 M 条边。

接下来为 M 行，每行包括三个整数，S、E 和 V，代表了从 S 节点可以单向直达 E 节点，并且权值为 V。

输出描述： 输出一个数，代表从起点到终点所花费的代价最小。

输入示例：

6 7
5 6 -2
1 2 1
5 3 1
2 5 2
2 4 -3
4 6 4
1 3 5

提示信息：

松弛

  • 本题依然是单源最短路问题，求 从 节点1 到节点n 的最小费用。 但本题不同之处在于 边的权值是有负数了。
  • Bellman_ford算法的核心思想是 对所有边进行松弛n-1次操作（n为节点数量），从而求得目标最短路。

何为松弛？

举一个例子，每条边有起点、终点和边的权值。例如一条边，节点A 到 节点B 权值为value，如图：

 
minDist[B] 表示 到达B节点 最小权值，minDist[B] 有哪些状态可以推出来？

  • 状态一： minDist[A] + value 可以推出 minDist[B]
  • 状态二： minDist[B]本身就有权值 （可能是其他边链接的节点B 例如节点C，以至于 minDist[B]记录了其他边到minDist[B]的权值）
  • minDist[B] 应为如何取舍，本题我们要求最小权值，那么 这两个状态我们就取最小的
    if (minDist[A] + value < minDist[B]) 
	minDist[B] = minDist[A] + value

也就是说，如果 通过 A 到 B 这条边可以获得更短的到达B节点的路径，即如果 minDist[A] + value < minDist[B]，那么我们就更新 minDist[B] = minDist[A] + value ，这个过程就叫做 “松弛” 。

其实都是围绕以下这句代码展开，这句代码就是 Bellman_ford算法的核心操作。

if (minDist[A] + value < minDist[B]) 
	minDist[B] = minDist[A] + value

以上代码也可以这么写：minDist[B] = min(minDist[A] + value, minDist[B])

而这思想，不就是动态规划思想吗， 即：将一个问题分解成多个决策阶段，通过状态之间的递归关系最后计算出全局最优解。

模拟过程

  • 我们依然使用 minDist 数组来表达 起点到各个节点的最短距离，例如minDist[3] = 5 表示起点到达节点3 的最小距离为5

0. 初始化

起点为节点1， 起点到起点的距离为0，所以 minDist[1] 初始化为0

 
以示例给出的所有边为例：

5 6 -2
1 2 1
5 3 1
2 5 2
2 4 -3
4 6 4
1 3 5

1. 松弛第一条边

边：节点5 -> 节点6，权值为-2，，minDist[5] 还是默认数值max，所以不能基于 节点5 去更新节点6，原图不变。

2. 松弛第二条边

边：节点1 -> 节点2，权值为1

对应程序：

if(minDits[1] + 1 < minDist[2])	//成立 minDist[1] = 0  0 + 1  < < MAX
	 minDist[2] = minDist[1] + 1 = 0 + 1 = 1;

3. 松弛第三条边

边：节点5 -> 节点3，权值为1 ，minDist[5] 还是默认数值max，所以不能基于节点5去更新节点3，保持上一轮的图

4. 松弛第四条边

边：节点2 -> 节点5，权值为2 ，minDist[5] > minDist[2] + 2 （经过上面的计算minDist[2]已经不是默认值，而是 1），更新 minDist[5] = minDist[2] + 2 = 1 + 2 = 3 ，如图：

5. 松弛第五条边

边：节点2 -> 节点4，权值为-3 ，minDist[4] > minDist[2] + (-3)，更新 minDist[4] = minDist[2] + (-3) = 1 + (-3) = -2 ，如图：

6. 松弛第六条边

边：节点4 -> 节点6，权值为4 ，minDist[6] > minDist[4] + 4，更新 minDist[6] = minDist[4] + 4 = -2 + 4 = 2

7. 松弛第七条边

边：节点1 -> 节点3，权值为5 ，minDist[3] > minDist[1] + 5，更新 minDist[3] = minDist[1] + 5 = 0 + 5 = 5 ，如图：

 
对所有边松弛一次，相当于计算 起点到达 与起点一条边相连的节点 的最短距离

上面的距离中，我们得到里 起点达到 与起点一条边相邻的节点2 和 节点3 的最短距离，分别是 minDist[2] = 1 和 minDist[3] = 5，但minDist[3]应该为4猜对呀，路径是节点1 -> 节点2 -> 节点5 -> 节点3

注意： 这里 说的是 一条边相连的节点，是路径走过一条边，不是直接一条边相连

对所有边松弛一次，相当于计算 起点到达 与起点路径只有一条边相连的节点 的最短距离

  • 与起点（节点1）一条边相邻的节点，到达节点2 最短距离是 1，到达节点3 最短距离是5。
  • 而 节点1 -> 节点2 -> 节点5 -> 节点3 这条路线 是 与起点 三条边相连的路线了。

总结：这里一条边是最短路径走一条边后的minDist数组。

同理，对所有的边松弛2次，就得到与节点路径走过2条边的最短路径，

同理对于节点数量为n，那么起点到终点，最多是 n-1 条边相连，对所有的边松弛 n - 1次，就能获得所有节点到源点的最短路径。

那么无论图是什么样的，边是什么样的顺序，我们对所有边松弛 n-1 次 就一定能得到 起点到达 终点的最短距离。

两个关键点

  • “松弛”究竟是个啥？
  • 为什么要对所有边松弛 n - 1 次 （n为节点个数） ？

程序实现：

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

// 边结构 存储边
struct Edge{
	int from;
	int to;
	int val;
};

int main()
{
	int n, m;
	cin >> n >> m;
	int s,t,k;
	
	vector<Edge> grid;
	while(m--)
	{
		cin >> s >> t >> k;
		grid.push_back(Edge{s,t,k});
	}

	int start = 1;  // 起点
	int end = n;    // 终点
	
	//记录每个节点到源点的最短路径
	vector<int> minDist(n+1, INT_MAX);
	minDist[start] = 0;
	// 对所有边 松弛 n-1 次
	for(int i = 1; i < n ; i++)
	{
		// 每一次松弛，都是对所有边进行松弛
		for(Edge edge: grid)
		{
			int from = edge.from;	// 边的出发点
			int to = edge.to;		// 边的到达点
			int val = edge.val;		// 边的权值
			//cout << from << "->" << to << ":" << val << endl;
			// 松弛操作 
			// minDist[from] != INT_MAX 防止从未计算过的节点出发
			if(minDist[from] != INT_MAX && minDist[from] + val < minDist[to])
				minDist[to] = minDist[from] + val;
		}
	}
	
//	for(int i = 0; i < n; i++){
//		cout << minDist[i] << " ";
//	}

	
	if (minDist[end] == INT_MAX) 
		cout << "unconnected" << endl; // 不能到达终点
	else 
		cout << minDist[end] << endl; // 到达终点最短路径
	return 0;
}

拓展

  • 那么松弛n次，n+1次呢，松弛 2 * n次呢，其实没啥影响，结果不会变的，（保证题中说明无任务父权回路的条件下）
  • 那么我们只要松弛 n - 1次 就一定能得到结果，没必要在松弛更多次了。
  • 至于负权回路 ，将在后续统一整理

4. Bellman_ford 队列优化算法（又名SPFA）

从上题看出，BF算法在松弛的时候，很多时间是不需要松弛的，真正需要松弛的边是基于已经计算过的节点的。

 
本图中，对所有边进行松弛，真正有效的松弛，只有松弛 边（节点1->节点2） 和 边（节点1->节点3） 。

而松弛 边（节点4->节点6） ，边（节点5->节点3）等等 都是无效的操作，因为 节点4 和 节点 5 都是没有被计算过的节点。

所以 Bellman_ford 算法 每次都是对所有边进行松弛，其实是多做了一些无用功。

只需要对 上一次松弛的时候更新过的节点作为出发节点所连接的边 进行松弛就够了。

用队列来记录上次松弛的时候更新过的节点

模拟过程

以示例给出的所有边为例：

5 6 -2
1 2 1
5 3 1
2 5 2
2 4 -3
4 6 4
1 3 5

我们依然使用minDist数组来表达 起点到各个节点的最短距离

初始化，起点为节点1， 起点到起点的最短距离为0，所以minDist[1] 为 0。 将节点1 加入队列 （下次松弛从节点1开始）

 
从队列里取出节点1，松弛节点1 作为出发点连接的边（节点1 -> 节点2）和边（节点1 -> 节点3）

  • 边：节点1 -> 节点2，权值为1 ，minDist[2] > minDist[1] + 1 ，更新 minDist[2] = minDist[1] + 1 = 0 + 1 = 1 。
  • 边：节点1 -> 节点3，权值为5 ，minDist[3] > minDist[1] + 5，更新 minDist[3] = minDist[1] + 5 = 0 + 5 = 5。

将节点2、节点3 加入队列，如图：

松弛节点2 作为出发点连接的边（节点2 -> 节点4）和边（节点2 -> 节点5）

  • 边：节点2 -> 节点4，权值为1 ，minDist[4] > minDist[2] + (-3) ，更新 minDist[4] = minDist[2] + (-3) = 1 + (-3) = -2 。
  • 边：节点2 -> 节点5，权值为2 ，minDist[5] > minDist[2] + 2 ，更新 minDist[5] = minDist[2] + 2 = 1 + 2 = 3 。

将节点4，节点5 加入队列，如图：

 

  • 通过分析发现，每次处理的逻辑是，取出队列的节点，计算到其相连节点的路径进行松弛判断，如果目标节点不在队列中则加入队列。
  • 因为这里注重的是处理相邻节点，因此在存储图的时候采用邻接表的方式存储图

程序实现：

#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <climits>

using namespace std;

//邻接表
struct Edge{
	int to;
	int val;
	Edge(int t, int w): to(t), val(w) {}  // 构造函数
};


int main()
{
	int n, m;
	cin >> n >> m;
		
	vector<list<Edge>> grid(n+1);
	int s,t,k;
	// 将所有边保存起来
	while(m--)
	{
		cin >> s >> t >> k;
		grid[s].push_back(Edge(t,k));
	}
	
	int start = 1;	// 起点
	int end = n;	// 终点
	
	vector<int> minDist(n+1, INT_MAX);
	minDist[start] = 0;
	
	queue<int> que;
	que.push(start); 
	
	while(!que.empty())
	{
		int cur = que.front();
		que.pop();
		for(Edge edge: grid[cur])
		{
			int from = cur;
			int to = edge.to;
			int val = edge.val;
			//cout << from << "->" << to << ":" << val << endl;
			// 开始松弛
			if(val + minDist[from] < minDist[to])
			{
				minDist[to] = val + minDist[from];
				que.push(to);
			}
		}
	}
	
//	for(int i = 0; i < n; i++){
//		cout << minDist[i] << " ";
//	}
	
	if(minDist[end] == INT_MAX)
		cout << "unconnected" << endl;
	else
		cout << minDist[end] << endl;
}

拓展

while (!que.empty()) 队里里 会不会造成死循环？ 例如 图中有环，这样一直有元素加入到队列里？

 

  • 其实有环的情况，要看它是 正权回路 还是 负权回路。
  • 对于正价环，即使元素重复加入队列，最后，也会因为 所有边都松弛后，节点数值（minDist数组）不在发生变化了 而终止
  • 对于负价环，如图，情况是就不一样了，出现负价环的情况在后续统一整理

5. Bellman_ford之判断负权回路

对于BF算法，存在一种特殊情况：负权回路

输入示例：

4 4
1 2 -1
2 3 1
3 1 -1
3 4 1

输出示例：

circle

思路

  • 如果在这样的图中求最短路的话， 就会在这个环里无限循环 （因为负数+负数 只会越来越小），无法求出最短路径。
  • 在BF基础算法中，最核心的是：对 所有边 进行 n-1 次松弛，求得源点到各个点路径的最短距离，同时拓展中提到对于无负权回路的图而言，循环 n 几次及其以上结果都是一样的。
  • 那么对于存在负价环的图而言，循环 n 次及其以上，结果与 n - 1 次就是有变化的。，因为 有负权回路就是可以无限最短路径（一直套圈）
  • 因此判断有无负价环的最直接的办法就是在BF算法的基础上再松弛一次，总共松弛 n 次，结果是否保持不变。

程序实现（程序是建立在BF算法的基础上上修改）

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

struct Edge{
	int from;
	int to;
	int val;
};

int main()
{
	int n, m;
	cin >> n >> m;
	int s,t,k;
	
	vector<Edge> grid;
	while(m--)
	{
		cin >> s >> t >> k;
		grid.push_back(Edge{s,t,k});
	}
	
	int start = 1;  // 起点
	int end = n;    // 终点
	
	vector<int> minDist(n+1, INT_MAX);
	minDist[start] = 0;
	// 对所有边 松弛 n 次
	bool flag = false;				// 判断是否有负
	for(int i = 1; i <= n ; i++)
	{
		// 每一次松弛，都是对所有边进行松弛
		for(Edge edge: grid)
		{
			int from = edge.from;	// 边的出发点
			int to = edge.to;		// 边的到达点
			int val = edge.val;		// 边的权值
			//cout << from << "->" << to << ":" << val << endl;
			// 松弛操作 
			// minDist[from] != INT_MAX 防止从未计算过的节点出发
			if(i < n)
			{
				if(minDist[from] != INT_MAX && minDist[from] + val < minDist[to])
					minDist[to] = minDist[from] + val;
			}
			else 	// 多加一次松弛判断负权回路
			{
				if(minDist[from] != INT_MAX && minDist[from] + val < minDist[to]) 
					 flag = true;
			}
		}
	}
	
//	for(int i = 0; i < n; i++){
//		cout << minDist[i] << " ";
//	}
	
	 if (flag) 							// 有负价环
		cout << "circle" << endl;
	if (minDist[end] == INT_MAX) 
		cout << "unconnected" << endl; 	// 不能到达终点
	else 
		cout << minDist[end] << endl; 	// 到达终点最短路径
	return 0;
}

拓展

本题可不可 使用 队列优化版的bellman_ford（SPFA）呢？

  • 上面的解法中，我们对所有边松弛了n-1次后，在松弛一次，如果出现minDist出现变化就判断有负权回路。
  • 如果使用 SPFA 那么节点都是进队列的，那么节点进入队列几次后 足够判断该图是否有负权回路呢？
  • 在SPFA算法中，极端情况下，即每个节点与其他节点都相连接，每个节点的入度为 n-1 （n为节点数量），所以每个节点最多加入 n-1 次队列。
  • 因此用SPFA判断是否存在负价环，只需要判断一个节点加入队列的次数超过 n - 1次即可。

程序实现：

#include <iostream>
#include <vector>
#include <climits>
#include <list>
#include <queue>

using namespace std;

//队列优化实现
struct Edge{
	int to;
	int val;
	Edge(int t,int v):to(t),val(v){}
};

int main()
{
	int n, m;
	cin >> n >> m;
	int p1,p2,val;
	// 使用邻接表 将所有边保存起来
	vector<list<Edge>> grid(n+1);
	while(m--)
	{
		cin >> p1 >> p2 >> val;
		grid[p1].push_back(Edge(p2,val));
	}
	
	int start = 1;  // 起点
	int end = n;    // 终点

	vector<int> minDist(n+1, INT_MAX);
	minDist[start] = 0;
	
	queue<int> que;				// 暂存要处理的节点队列 
	que.push(start);			// 初始化队列
	
	vector<int> count(n+1, 0);	// 记录节点加入队列几次
	count[start]++;
	
	bool flag = false;			// 标记是否有负价环
	while(!que.empty())
	{
		//获取当前要处理的节点
		int cur = que.front();
		que.pop();

//		for(int i = 1; i <= n; i++)
//			cout << minDist[i] << " ";
//		cout << endl;
		
		//获取节点所连接的所有边
		for(Edge edge: grid[cur])
		{
			int from = cur;
			int to = edge.to;
			int val = edge.val;
			//松弛
			if(minDist[from] + val < minDist[to])
			{
				//cout << from << "->" << to << ":" << val << endl;
				minDist[to] = minDist[from] + val;
				que.push(to);
				count[to]++;
				// 如果加入队列次数超过 n-1次 就说明该图与负权回路
				if(count[to] == n) 
				{
					flag = true;
					while(!que.empty()) 
						que.pop();
					break;
				}
			}
 		}
	}
	
//	for(int i = 0; i < n; i++){
//		cout << minDist[i] << " ";
//	}
	if (flag) 
		cout << "circle" << endl;
	else if (minDist[end] == INT_MAX) 
		cout << "unconnected" << endl; 	// 不能到达终点
	else 
		cout << minDist[end] << endl; 	// 到达终点最短路径
	return 0;
}

6. Bellman_ford之单源有限最短路

上题只通过基础的BF和SPFA算法判断了是否存在负价环，而未对后续结果集minDist数组做进一步研究，本题就将对后续的minDist数组做进一步深入研究。

题意：
请计算在最多经过 k 个节点的条件下，从节点src 到节点 dst 的最低代价。

输入描述：
第一行包含两个正整数，第一个正整数 n 表示 n 个节点，第二个整数 m 表示这些节点中有 m 条边。

接下来为 m 行，每行包括三个整数，s、t 和 v，表示 s 节点到节点，代价为 v

最后一行包含三个正整数，src、dst、和 k，src 和 dst 为节点，从 src 到 dst 经过的节点数量限制。

输出描述：
输出一个整数，表示从节点src 到节点dst 的最低代价，如果无法在给定经过节点数量限制下找到从 src 到 dst 的路径，则输出 “unreachable”，表示不存在符合条件的路径。

输入示例：

6 7
1 2 1
2 4 -3
2 5 2
1 3 5
3 5 1
4 6 4
5 6 -2
2 6 1

输出示例：

0

思路

  • 题目中描述是 最多经过 k 个城市的条件下，而不是一定经过k个城市，也可以经过的城市数量比k小，但要最短的路径。
  • 对所有边松弛一次，相当于计算 起点到达 与起点一条边相连的节点 的最短距离。
  • 本题是最多经过 k 个节点， 那么是 k + 1条边相连的节点
  • 所以本题就是求：起点最多经过k + 1 条边到达终点的最短距离。
  • 那么对所有边松弛 k + 1次，就是求 起点到达 与起点k + 1条边相连的节点的 最短距离

但是如果直接将BF算法的循环次数改成 k + 1是有问题的，因为题目可能存在负价环。

接下来我们拿这组数据来举例：

4 4
1 2 -1
2 3 1
3 1 -1
3 4 1
1 4 3

 
实际 mindDist[4] = 1，节点1 -> 节点2 -> 节点3 -> 节点4

经过对所有边松弛一次：

在这里插入图片描述
 

  • 所有边进行的第二次松弛，minDist数组为 ： -2 -2 -1 0
  • 所有边进行的第三次松弛，minDist数组为 ： -3 -3 -2 -1
  • 所有边进行的第四次松弛，minDist数组为 ： -4 -4 -3 -2

理论上来说，对所有边松弛一轮，相当于计算 起点到达 与起点一条边相连的节点 的最短距离。

但在对所有边松弛第一次的过程中，发现不仅仅 与起点一条边相连的节点更新了，所有节点都更新了。

在下面画图距离中，对所有边进行第一次松弛，在计算 边（节点2 -> 节点3） 的时候，更新了 节点3。

 

理论上来说节点3 应该在对所有边第二次松弛的时候才更新。 这因为当时是基于已经计算好的 节点2（minDist[2]）来做计算了。

minDist[2]在计算边：（节点1 -> 节点2）的时候刚刚被赋值为 -1。

这样就造成了一个情况，即：计算minDist数组的时候，基于了本轮前面一次松弛的 minDist最新的数值，而不是上一轮 松弛时候minDist的数值。

所以在每次计算 minDist 时候，要基于 对所有边上一轮松弛的 minDist 数值才行，所以我们要记录上一轮松弛的 minDist。

程序实现：

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

struct Edge{
	int from;
	int to;
	int val;
	Edge(int x, int y, int k):from(x),to(y),val(k){}
};

int main()
{
	int n, m;
	cin >> n >> m;
	
	vector<Edge> grid;
	int s, t, v;
	while(m--)
	{
		cin >> s >> t >> v;
		grid.push_back(Edge{s, t, v});
	}
	int src, dst, k;
	cin >> src >> dst >> k;

	vector<int> minDist(n+1, INT_MAX);
	//松弛 k + 1 次
	minDist[src] = 0;
	// 用来记录上一次遍历的结果
	 vector<int> minDist_copy(n + 1); 
	for(int i = 0; i <= k; i++)
	{
		minDist_copy = minDist;			// 获取上一次计算的结果
		for(Edge edge: grid)
		{
			int from = edge.from;
			int to   = edge.to;
			int val  = edge.val;
			// 注意使用 minDist_copy 来计算 minDist 
			if(minDist_copy[from] != INT_MAX && minDist_copy[from] + val < minDist[to])
				minDist[to] = minDist_copy[from] + val;
		}
	}
	
	if(minDist[dst] == INT_MAX)
		cout << "unreachable" << endl;
	else
		cout << minDist[dst]  << endl;
	
	return 0;
}

☆ 拓展

拓展1（边顺序的影响）

其实边的顺序会影响我们每一次拓展的结果。

以下两个示例构成同样的图，不同的输入顺序，再用基础BF基础版的程序实现，示例二是对的。

示例一：

4 4
1 2 -1
2 3 1
3 1 -1
3 4 1
1 4 3

示例2：

4 4
3 1 -1
3 4 1
2 3 1
1 2 -1
1 4 3

所构成是图是一样的，都是如下的这个图，但给出的边的顺序是不一样的

示例1：
第一轮：

  • 1 2 -1: 计算minDist[2] = minDist[1] + -1 = -1 < MAX，minDist[2] = -1
  • 2 3 1: 计算minDist[3] = minDist[2] + 1 = -1 + 1 = 0 < MAX，minDist[3] = 0
  • 3 1 -1: 计算minDist[1] = minDist[3] + -1 = 0 + -1 = -1 < MAX，minDist[1] = -1

示例2：
第一轮：

  • 3 1 -1: 节点3 -> 节点1，不松弛，minDits[3] = MAX
  • 3 4 1：节点3 -> 节点4，不松弛，minDits[3] = MAX
  • 2 3 1：节点2 -> 节点3，不松弛，minDits[2] = MAX
  • 1 2 -1：节点1 -> 节点2，松弛，minDits[2] = -1

通过以上的对比， 清晰的看到，示例一每一轮的跟新的数据存在本轮刚计算出的结果，而示例二则不存在这种情况。因此这里很清晰的理解了为需要 minDist_copy 这个数组来保存上一轮松弛的结果了。

并且，同样的图，对于不同的输入，基础BF的写法是有缺陷的。

拓展2（本题本质）

那么前面讲解过1. 也是 bellman_ford经典算法，也没使用 minDist_copy，怎么就没问题呢？

前面的图是没有负权回路的，那么多松弛多少次，对结果都没有影响

为什么前面的3. 判断负权回路，有负价环但没有使用minDist_copy

题目3中是判断是否有 负权回路，一旦有负权回路， 对所有边松弛 n-1 次以后，在第 n 轮做松弛 minDist 数值一定会变，根据这一点来判断是否有负权回路

题3只需要判断minDist数值变化了就行，而 minDist 的数值对不对，并不是我们关心的。 所以也不需要 minDist_copy

那么本题 为什么计算minDist 一定要基于上次 的 minDist 数值。

其关键在于本题的两个因素：

  • 本题可以有负权回路，说明只要多做松弛，结果是会变的。
  • 本题要求最多经过k个节点，对松弛次数是有限制的。

拓展3（SPFA）

  • 本题也可以用 SPFA来做，在使用SPFA算法解决本题的时候，关键在于 如何控制松弛k次。
  • 不难，但有点技巧，可以用一个变量 que_size 记录每一轮松弛入队列的所有节点数量。
  • 下一轮松弛的时候，就把队列里 que_size 个节点都弹出来，就是上一轮松弛入队列的节点。

拓展4（能否用dijkstra）

dijkstra 是贪心的思路 每一次搜索都只会找距离源点最近的非访问过的节点。

如果限制最多访问k个节点，那么 dijkstra 未必能在有限次就能到达终点，即使在经过k个节点确实可以到达终点的情况下。

在以下这个图中，求节点1 到 节点7 最多经过2个节点 的最短路是多少呢？最短路显然是：

 
如果是 dijkstra 求解的话，求解过程是这样的：

  • 初始化如图所示：

  • 找距离源点最近且没有被访问过的节点，先找节点1

  • 距离源点最近且没有被访问过的节点，找节点2

  • 距离源点最近且没有被访问过的节点，找到节点3

  • 距离源点最近且没有被访问过的节点，找到节点4

 
此时最多经过2个节点的搜索就完毕了，但结果中minDist[7] （即节点7的结果）并没有被更。

那么 dijkstra 会告诉我们 节点1 到 节点7 最多经过2个节点的情况下是不可到达的。

通过以上模拟过程，感受到 dijkstra 贪心的过程，正是因为 贪心，所以 dijkstra 找不到 节点1 -> 节点2 -> 节点6-> 节点7 这条路径。

7. Floyd算法

输入描述：

  • 第一行包含两个整数 N, M, 分别表示节点的数量和边的的数量。
  • 接下来的 M 行，每行包含三个整数 u, v, w，表示节点 u 和节点 v 之间有一条长度为 w 的双向边。
  • 接下里的一行包含一个整数 Q，表示起点的组别有Q个。
  • 接下来的 Q 行，每行包含两个整数 start, end，表示一组的起点和终点。
  • 求每一组起点start到终点end的最短路径

输出描述：

  • 对于每一组的起点和终点，输出一行表示从起点到终点的最短路径长度。如果两个节点之间不存在路径，则输出 -1。

输入示例：

7 3 
1 2 4
2 5 6
3 6 8
2 
1 2 
2 3

输出示例：

4 
-1

提示信息： 1 <= N, M, Q <= 1000.

思路

  • 本题是经典的多源最短路问题。，之前的最短路径问题中的起点只有一个，而本题拥有多个起点，因此需要使用 Floyd 算法。
  • Floyd 算法对边的权值正负没有要求，都可以处理。
  • Floyd算法核心思想是动态规划
  • 例如我们再求节点1 到 节点9 的最短距离，用二维数组来表示即：grid[1][9]，如果最短距离是10 ，那就是 grid[1][9] = 10
  • 那 节点1 到 节点9 的最短距离：可以由 节点1 到节点5的最短距离 + 节点5到节点9的最短距离组成，即 grid[1][9] = grid[1][5] + grid[5][9]
  • 节点1 到节点5的最短距离：可以由节点1 到 节点3的最短距离 + 节点3 到 节点5 的最短距离组成，即 grid[1][5] = grid[1][3] + grid[3][5]

动规五部曲

1. 确定dp数组以及下标的含义： grid[i][j][k] = m，表示 节点 i 到 节点 j 以[1…k] 集合为中间节点的最短距离为m。

  • 节点i 到 节点j 的最短路径中 一定是经过很多节点，那么这个集合用[1…k] 来表示
  • 这里的 k 不能单独指某个节点，k 一定要表示一个集合，即[1…k] ，表示节点1 到 节点k 一共k个节点的集合。

 
2. 确定递推公式
我们分两种情况：

  • 节点 i 到 节点 j 的最短路径经过节点k
  • 节点 i 到 节点 j 的最短路径不经过节点k

对于第一种情况： grid[i][j][k] = grid[i][k][k - 1] + grid[k][j][k - 1]

  • 节点i 到 节点k 的最短距离 是不经过节点k，中间节点集合为[1…k-1]，所以 表示为grid[i][k][k - 1]
  • 节点k 到 节点j 的最短距离 也是不经过节点k，中间节点集合为[1…k-1]，所以表示为 grid[k][j][k - 1]

第二种情况： grid[i][j][k] = grid[i][j][k - 1]

  • 如果节点i 到 节点j的最短距离 不经过节点k，那么 中间节点集合[1…k-1]，表示为 grid[i][j][k - 1]

因为我们是求最短路，对于这两种情况自然是取最小值，即：

grid[i][j][k] = min(grid[i][k][k - 1] + grid[k][j][k - 1]， grid[i][j][k - 1])

3. dp数组初始化

  • grid[i][j][k] = m，表示 节点i 到 节点j 以[1…k] 集合为中间节点的最短距离为m，刚开始初始化k 是不确定的。

  • 所以 只能 把 k 赋值为 0，本题 节点0 是无意义的，节点是从1 到 n。

  • grid数组是一个三维数组，那么我们初始化的数据在 i 与 j 构成的平层，如图：

     

  • 所以初始化代码：

    int n, m;
cin >> n >> m;
// C++定义了一个三位数组
//本题求的是最小值，所以输入数据没有涉及到的节点的情况都应该初始为一个最大数。
//这样不会影响，每次计算取最小值的时候 初始值对计算结果的影响。
vector<vector<int>> grid(n+1,vector<int>(n+1, 10005));	//10005是因为边的最大距离是10^4
int u,v,w;
while(m--)
{
	cin >> u >> v >> w;
	grid[u][v] = w;
	grid[v][u] = w;
}

  • 本题求的是最小值，所以输入数据没有涉及到的节点的情况都应该初始为一个最大数。这样才不会影响每次计算的影响，所以grid数组的定义可以是：

    // 定义了一个三位数组，10005是因为边的最大距离是10^4
vector<vector<vector<int>>> grid(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, 10005)));

4. 确定遍历顺序

  • k 依赖于 k - 1， i 和 j 的到 并不依赖与 i - 1 或者 j - 1 等等。

  • 三位坐标i，j，k，相当于 i 和 j 是平层，而 k 是 垂直向上 的

  • 所以遍历 k 的 for循环一定是在最外面，这样才能一层一层去遍历。如图：

  • 至于遍历 i 和 j 的话，for 循环的先后顺序无所谓，代码如下：

    //Floyd算法
for(int k = 1; k <= n; k++){
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++)
			grid[i][j] = min(grid[i][j], grid[i][k] + grid[k][j]);
	}
}

  • 如果把 k 放在里面，此时就遍历了 j 与 k 形成一个平面，i 则是纵面，如果以 k 和 j 形成的平面去一层一层遍历，如图：

  • 就造成了 递推公式 用不上上一轮计算的结果(因为 k 是依赖于 k-1的)，从而导致结果不对，如果点遍历错误：

完整程序实现：

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

int main()
{
	int n, m;
	cin >> n >> m;
	// C++定义了一个三位数组
	//本题求的是最小值，所以输入数据没有涉及到的节点的情况都应该初始为一个最大数。
	//这样不会影响，每次计算取最小值的时候 初始值对计算结果的影响。
	vector<vector<vector<int>>> grid(n+1, vector<vector<int>>(n+1, vector<int>(n+1, 10005)));
	int u,v,w;
	while(m--)
	{
		cin >> u >> v >> w;
		grid[u][v][0] = w;
		grid[v][u][0] = w;
	}
	
	//Floyd算法
	for(int k = 1; k <= n; k++)
	{
		for(int i = 1; i <= n; i++)
		{
			for(int j = 1; j <= n; j++)
				grid[i][j][k] = min(grid[i][j][k-1], grid[i][k][k-1] + grid[k][j][k-1]);
		}
	}
	
	// 输出结果
	int q;
	int start,end;
	cin >> q;
	while(q--)
	{
		cin >> start >> end;
		if(grid[start][end][n] == 10005)
			cout << -1 << endl;
		else
			cout << grid[start][end][n] << endl;
	}
	
	return 0;
}

空间优化

  • 从滚动数组的角度来看，定义一个 grid[n + 1][ n + 1][2] 这么大的数组就可以，因为k 只是依赖于 k-1的状态，并不需要记录k-2，k-3，k-4 等等这些状态。

  • 只需要记录 grid[i][j][1] 和 grid[i][j][0] 就好，之后就是 grid[i][j][1] 和 grid[i][j][0] 交替滚动。

  • 再进一步，如果本层刚计算好的 grid[i][k] 比上一层 （即k-1层）计算的 grid[i][k] 小，说明确实有 i 到 k 的更短路径，那么基于更小的 grid[i][k] 去计算 gird[i][j] 没有问题。

  • 如果 本层刚计算好的 grid[i][k] 比上一层 （即k-1层）计算的 grid[i][k] 大， 这不可能，因为这样也不会做更新 grid[i][k]的操作。

  • 所以本层计算中，使用了本层计算过的 grid[i][k] 和 grid[k][j] 是没问题的。

  • 那么就没必要区分，grid[i][k] 和 grid[k][j] 是 属于 k - 1 层的呢，还是 k 层的。

所以递归公式可以为：

grid[i][j] = min(grid[i][j], grid[i][k] + grid[k][j]);

基于二维数组的本题代码为：

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

//优化
int main()
{
	int n, m;
	cin >> n >> m;
	// C++定义了一个三位数组
	//本题求的是最小值，所以输入数据没有涉及到的节点的情况都应该初始为一个最大数。
	//这样不会影响，每次计算取最小值的时候 初始值对计算结果的影响。
	vector<vector<int>> grid(n+1,vector<int>(n+1, 10005));	//10005是因为边的最大距离是10^4
	int u,v,w;
	while(m--)
	{
		cin >> u >> v >> w;
		grid[u][v] = w;
		grid[v][u] = w;
	}
	
	//Floyd算法
	for(int k = 1; k <= n; k++){
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++)
				grid[i][j] = min(grid[i][j], grid[i][k] + grid[k][j]);
		}
	}
	
	// 输出结果
	int q;
	int start,end;
	cin >> q;
	while(q--)
	{
		cin >> start >> end;
		if(grid[start][end] == 10005)
			cout << -1 << endl;
		else
			cout << grid[start][end] << endl;
	}
	
	return 0;
}
  • 理解了遍历顺序才是Floyd算法最精髓的地方。
  • floyd算法的时间复杂度相对较高，适合 稠密图且源点较多的情况。
  • 二维数组降低了空间复杂度，三维数组更于理解整个过程，二维数组在遍历顺序是说不清的。

8. A* 算法

题目描述：

  • 在象棋中，马和象的移动规则分别是“马走日”和“象走田”。
  • 现给定骑士的起始坐标和目标坐标，要求根据骑士的移动规则，计算从起点到达目标点所需的最短步数。
  • 骑士移动规则如图，红色是起始位置，黄色是骑士可以走的地方。
  • 棋盘大小 1000 x 1000（棋盘的 x 和 y 坐标均在 [1, 1000] 区间内，包含边界）

输入描述：

  • 第一行包含一个整数 n，表示测试用例的数量。
  • 接下来的 n 行，每行包含四个整数 a1, a2, b1, b2，分别表示骑士的起始位置 (a1, a2) 和目标位置 (b1, b2)。

输出描述：
输出共 n 行，每行输出一个整数，表示骑士从起点到目标点的最短路径长度。

输入示例：

6
5 2 5 4
1 1 2 2
1 1 8 8
1 1 8 7
2 1 3 3
4 6 4 6

输出示例：

2
4
6
5
1
0

思路

  • 这道题目的第一个想法就是广搜，这也是最经典的广搜类型题目大，但广搜中做了很多无用的遍历，

  • 如图， 黄色的格子是广搜遍历到的点，这里我们能不能遍历方向，向着终点的方向去遍历呢？ 而A*算法做到了这一点

  • 而 Astar 关键在于 启发式函数， 也就是 影响 广搜或者 dijkstra 从 容器（队列）里取元素的优先顺序。

  • 搜索过程是这样的，如图，图中着色的都是我们要遍历的点。

 
为了可以明显看到区别，卡哥将 BFS 和 A * 制作成可视化动图，大家可以自己看看动图，效果更好，网址：https://kamacoder.com/tools/knight.html

启发函数

那么 A * 为什么可以有方向性的去搜索，它的如何知道方向呢？

其关键在于 启发式函数。

指引 搜索的方向的关键代码在这里：

int m=q.front();q.pop();

从队列里取出什么元素，接下来就是从哪里开始搜索。

所以 启发式函数 要影响的就是队列里元素的排序，这是影响BFS搜索方向的关键。

对队列里节点进行排序，需要给每一个节点权值，如何计算权值呢？

每个节点的权值为F，给出公式为：F = G + H

G：起点达到目前遍历节点的距离

F：目前遍历的节点到达终点的距离

起点到达终点的距离 = 起点达到目前遍历节点的距离 + 目前遍历的节点到达终点的距离

计算两点距离通常有如下三种计算方式：

  • 曼哈顿距离，计算方式： d = ∣ x 1 − x 2 ∣ + ∣ y 1 − y 2 ∣ d = |x_1-x_2|+|y_1-y_2| d=∣x1​−x2​∣+∣y1​−y2​∣
  • 欧氏距离（欧拉距离） ，计算方式： d = ( x 1 − x 2 ) 2 + ( y 1 − y 2 ) 2 d = \sqrt{(x_1-x_2)^2 + (y_1-y_2)^2 } d=(x1​−x2​)2+(y1​−y2​)2 ​
  • 切比雪夫距离，计算方式： d = m a x ( ∣ x 1 − x 2 ∣ , ∣ y 1 − y 2 ∣ ) d = max(|x_1 - x_2|, |y_1 - y_2|) d=max(∣x1​−x2​∣,∣y1​−y2​∣)

选择哪一种距离计算方式 可能也会导致 A * 算法的结果不同，本题，采用欧拉距离，能最大程度体现点与点之间的距离。

程序实现

（一）节点定义

  • 对于跳到任意一格（节点），有自身的坐标属性 x 和 y，也有A*距离，包括起点到该点的距离G，该点到终点的预估距离H，以及起点到终点的总距离F，因此对于一个节点，封装结构体，有以上5个参数
    struct Node{
	int x,y;		//起始点
	int g,h,f;		//A*距离
};
  • 在队列中，需要根据节点权值对队列进行排序，使其距离最小的节点拥有最高优先级
    struct Node{
	int x,y;		//起始点
	int g,h,f;		//A*距离
	// 重载运算符， 从小到大排序    处理最小值
	bool operator < (const Node& other) const
	{
		return other.f < f;		// 较小的节点权值f应该有较高的优先级  
	}
};

（二）启发函数

  • 启发函数用于计算当前节点到终点的距离，这里使用欧氏距离
    //当前节点到终点的欧拉距离
// 统一不开根号，这样可以提高精度
int Heuristic(const Node& node)
{
	return (node.x - b1) * (node.x - b1) + (node.y - b2) *  (node.y - b2) ;
}

完整程序实现：
A* 算法是基于对bfs的优化，因此A*算法的函数是bfs的框架，遗忘了先巩固一下bfs程序。

#include <iostream>
#include <vector>
#include <string.h>
#include <queue>

using namespace std;

int moves[1001][1001];		// 到下个节点的最短步数
int b1,b2;					// 下一个节点坐标
// 题意的8个方向
int dir[8][2]={-2,-1,-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,-2};
// F = G + H
// G = 从起点到该节点路径消耗
// H = 该节点到终点的预估消耗

struct Node{
	int x,y;		//起始点
	int g,h,f;		//A*距离
	// 重载运算符， 从小到大排序    处理最小值
	bool operator < (const Node& other) const
	{
		return other.f < f;		// 较小的节点权值f应该有较高的优先级  
	}
};

priority_queue<Node> que;		// 优先级队列

//当前节点到终点的欧拉距离
// 统一不开根号，这样可以提高精度
int Heuristic(const Node& node)
{
	return (node.x - b1) * (node.x - b1) + (node.y - b2) *  (node.y - b2) ;
}

// A*算法入口
void astar(const Node& node)
{
	Node cur, next;				//当前节点 下个节点
	que.push(node);
	while(!que.empty())
	{
		// 获取优先级队列中距离最近的节点
		cur = que.top();
		que.pop();
		// 到达终点
		if(cur.x == b1 && cur.y == b2)
			break;
		// 遍历不同的方向
		for(int i = 0; i < 8; i++)
		{
			next.x = cur.x + dir[i][0];
			next.y = cur.y + dir[i][1];
			// 越界
			if(next.x < 1 || next.y < 1 || next.x > 1000 || next.y > 1000)
				continue;
			if(!moves[next.x][next.y])
			{
				moves[next.x][next.y] = moves[cur.x][cur.y] + 1;	// 步数 + 1
				//开始计算F
				next.g = cur.g + 5;			// 统一不开根号，可以提高精度，马走日，1 * 1 + 2 * 2 = 5
				next.h = Heuristic(next);	// 计算下个点到终点的启发式函数距离
				next.f = next.g  + next.h;	// 计算下个节点的 f
				que.push(next);				// 下个节点加入优先级队列
			}	
		}
	}
}

int main()
{
	int n,a1,a2;
	cin >> n;
	while(n--)
	{
		cin >> a1 >> a2 >> b1 >> b2;
		memset(moves, 0, sizeof(moves));
		Node start;
		start.x = a1;
		start.y = a2;
		start.g = 0;
		start.h = Heuristic(start);
		start.f = start.g + start.h;
		astar(start);
		//清空队列
		while(!que.empty())
			que.pop();
		cout << moves[b1][b2] << endl;
	}
	return 0;
}

拓展

  • A * 算法 并不是一个明确的最短路算法，A * 算法搜的路径如何，完全取决于 启发式函数怎么写。
  • A * 算法并不能保证一定是最短路，因为在设计 启发式函数的时候，要考虑 时间效率与准确度之间的一个权衡。
  • 虽然本题中，A * 算法得到是最短路，也是因为本题 启发式函数 和 地图结构都是最简单的。
  • 在大型游戏设计中， 保证运行效率的情况下，A * 算法中的启发式函数 设计往往不是最短路，而是接近最短路的 次短路设计。

A * 的缺点：

  • 相对了 普通BFS，A * 算法只从 队列里取出 距离终点最近的节点。
  • A * 在一次路径搜索中，大量不需要访问的节点都在队列里，会造成空间的过度消耗。
  • 如果题目中，给出 多个可能的目标，然后在这多个目标中 选择最近的目标，这种 A * 就不擅长了， A * 只擅长给出明确的目标 然后找到最短路径。

总结

1. 最短路算法总结篇
2. 图论总结

最短路径总结：

  • dijkstra朴素版
  • dijkstra堆优化（优先级队列）
  • Bellman_ford
  • Bellman_ford 队列优化算法（又名SPFA）
  • bellman_ford 算法判断负权回路
  • bellman_ford之单源有限最短路
  • Floyd 算法
  • 启发式搜索：A * 算法

最短路径算法的使用场景：

适合图的大小边的权值为负数检测复权回路有限节点最短路径源点数时间复杂度
dijkstra朴素版稠密图不可以不可以不可以单源 O ( N 2 ) O(N^2) O(N2), N为节点数
dijkstra堆优化稀疏图不可以不可以不可以单源 O ( E l o g E ) O(ElogE) O(ElogE), E为边数
Bellman_ford稠密图可以可以可以单源 O ( N ∗ E ) O(N*E) O(N∗E), N为节点数，E为边数
SPFA稀疏图图可以可以可以单源 O ( K ∗ N ) O(K*N) O(K∗N), K为不定值，取决于图的稠密度
Floyd稠密图可以可以不可以多源 O ( n 3 ) O(n^3) O(n3), n为节点数
  • A* 属于启发式搜索，和上面最短路算法并不是一类

标签：图论,cur,int,源点,BF,SPFA,minDist,grid,节点
From： https://blog.csdn.net/weixin_46216674/article/details/142517573

相关文章

  • 图论优化
    图论优化三元环计数首先给所有边定向，从度数小的点指向度数大的点，如果度数一样，则从编号小的指向编号大的，最终形成一张DAG。枚举\(u\)以及\(u\)指向的点\(v\)以及\(v\)指向的点\(w\)，如果\(u\)也指向\(w\)则成三元环。如果要一开始是有向图计数则最后判断一下\(u,v,w\)的方向即可......
  • DFS与BFS
    图论：一、图中DFS与BFS数和图的存储方式：m与n^2一个级别属于稠密图，m与n一个级别则属于稀疏图，可以从题目中明显看出来稠密图：邻接矩阵稀疏图：邻接表#include<bits/stdc++.h>usingnamespacestd;constintN=100100;intm,n;inth[N],e[N],ne[N],idx;intq[N],d[N];bool......
  • 代码随想录算法训练营 | 图论理论基础，98. 所有可达路径
    图论理论基础1.图的种类：有向图，无向图，加权有向图，加权无向图；2.度：无向图中有几条边连接该节点，该节点就有几度，在有向图中，每个节点有出度和入度；出度：从该节点出发的边的个数；入度：指向该节点边的个数；3.连通图：在无向图中，任何两个节点都是可以到达的；强连通图：在有向图中，任何两个节点是可以......
  • ABF第一章
    布尔函数的傅里叶展开我们先来看几个例子。考虑几个简单的定义在\(f:\{-1,1\}^n\rightarrow\{-1,1\}\)的函数。\(n=2\)，\(f\)定义为向量的最大值。那么\(f=\frac{1}{2}+\frac{1}{2}x_1+\frac{1}{2}x_2-\frac{1}{2}x_1x_2\)。其实我感觉这个展开方式更泰勒一点......\(n=3\)，\(f......
  • 图论模板
    最短路（dijkstra）无法处理负边权，时间复杂度O(mlogn)#include<bits/stdc++.h>#definefo(i,a,b)for(ll(i)=(a);(i)<=(b);(i)++)#definefd(i,b,a)for(ll(i)=(b);(i)>=(a);(i)--)#definelc(o<<1)#definerc((o<<1)|1)#definemk(x,y)make_pair((x),(......
  • RBFN
    下面我们详细讲解这个实现径向基函数神经网络（RBFN）的代码，并结合数学公式来说明每个部分的作用。一、RBFN简介径向基函数神经网络（RBFN）是一种前馈神经网络，通常包含三层：输入层：直接将输入数据传递到隐藏层。隐藏层：由一组径向基函数组成，每个函数都有一个中心（centers）和宽度（sigma）。......
  • A*，spfa，和如何利用spfa判断负环
    A*即是在dij的思路上加上预估函数注意：此处的欧式距离即为max(|x1-x2|,|y1-y2|); spfa算法每个点至多被松弛n-1次；我们利用队列来记录哪些点被松弛过（因为被松弛过说明距离变的更小，就有机会更新别人），一个点一旦出队，即取消标记那么我们又该如何判断负环呢？......
  • 图论基础
    定义与记号涉及常见或可能用到的概念的定义。关于更多，见参考资料。基本定义图：一张图\(G\)由若干个点和连接这些点的边构成。称点的集合为点集\(V\)，边的集合为边集\(E\)，记\(G=(V,E)\)。阶：图\(G\)的点数\(|V|\)称为阶，记作\(|G|\)。无向图：若\(e\inE\)没有......
  • 图论之搜索遍历
    前言一个重要的板块，倒是有很多有趣的题，从搜索开始吧MazeTacToeS暴力即可，\(3^9\times25\times25\)绰绰有余，把状态转换为三进制\(dfs\)ConnectedComponents?根据鸽巢原理，必定有一个点被割去的边\(\le\frac{m}{n}\),然后我们找到这个点，对于连接他的边均在同一个联......
  • 01 bfs 学习笔记
    当一张图的边权只有\(0\)和\(1\)时，跑dij的堆优化显得比较累赘。因为只有两个取值，所以取\(0\)的时候在队列前面推进来，反之在后面。其他和dij没什么区别，时间复杂度\(O(m)\)，其中\(m\)是边数。相关题目：P4554小明的游戏。点击查看代码voidwork(){ m0(vis);mem(di......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99