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)$，可以看出时间复杂度 只和 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=\sqrt{(x_1-x_2{)}^2+(y_1-y_2{)}^2}$
• 切比雪夫距离，计算方式：$d=max(|x_1-x_2|,|y_1-y_2|)$

选择哪一种距离计算方式 可能也会导致 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)$, N为节点数
dijkstra堆优化	稀疏图	不可以	不可以	不可以	单源	$O(ElogE)$, E为边数
Bellman_ford	稠密图	可以	可以	可以	单源	$O(N\ast E)$, N为节点数，E为边数
SPFA	稀疏图图	可以	可以	可以	单源	$O(K\ast N)$, K为不定值，取决于图的稠密度
Floyd	稠密图	可以	可以	不可以	多源	$O(n^3)$, n为节点数

• A* 属于启发式搜索，和上面最短路算法并不是一类