数据结构 —— FloydWarshall算法

数据结构 —— FloydWarshall算法

• FloydWarshall算法
• 三种最短路径算法比较
• • • 1. Dijkstra算法
    • 2. Bellman-Ford算法
    • 3. Floyd-Warshall算法
    • 总结

我们之前介绍的两种最短路径算法都是单源最短路径，就是我们要指定一个起点来寻找最短路径，而我们今天介绍的FloydWarshall算法，可以不指定源点，找到最短路径：

FloydWarshall算法

在介绍FloydWarshall算法之前，我们先来想一个问题，就是：最短路径要经过多少顶点呢？
第一种情况他俩之间就是最短距离：

第二种，中间经过了许多结点：

Floyd-Warshall算法是一种在有向图中寻找所有顶点对之间的最短路径的算法。它可以在图中包含负权边的情况下工作，但是图中不能包含负权循环。

以下是Floyd-Warshall算法的基本步骤：

1. 初始化：创建一个n×n的距离矩阵D，其中D[i][j]表示从顶点i到顶点j的最短路径的长度。如果(i,j)之间没有直接的边，则D[i][j]设置为无穷大。对于所有的顶点i，D[i][i]=0。

2. 对于每一个中间顶点k，更新距离矩阵D。具体来说，对于每一对顶点(i, j)，如果D[i][j] > D[i][k] + D[k][j]，则更新D[i][j]为D[i][k] + D[k][j]。这相当于检查是否可以通过k作为中间顶点来获得从i到j的更短路径。

3. 重复步骤2，直到所有可能的中间顶点都被考虑过。

4. 最后，距离矩阵D中的每个元素D[i][j]将包含从顶点i到顶点j的最短路径的长度。

void FloydWarshall(vector<vector<W>>& vvDest, vector<vector<int>>& vvParentpath) {     // 调整vvDest和vvParentpath的大小与顶点数量一致     vvDest.resize(_vertex.size());     vvParentpath.resize(_vertex.size());      // 初始化距离矩阵为最大权重（表示不可达）     // 初始化前驱节点矩阵为-1（表示无前驱节点）     for (size_t i = 0; i < _vertex.size(); i++)     {         vvDest[i].resize(_vertex.size(), MAX_W);         vvParentpath[i].resize(_vertex.size(), -1);     }      // 初始化距离矩阵和前驱节点矩阵     // 如果两个顶点间存在直接连接，则设置距离矩阵的相应位置为该连接的权重     // 并且设置前驱节点为当前顶点     for (size_t i = 0; i < _vertex.size(); i++)     {         for (size_t j = 0; j < _vertex.size(); j++)         {             // 同一顶点到自身的距离为0，前驱节点为-1             if (i == j)             {                 vvDest[i][j] = 0;                 vvParentpath[i][j] = -1;             }              // 如果两顶点之间有直接连接，并且权重不是最大权重（即可达）             if (_matrix[i][j] != MAX_W)             {                 vvDest[i][j] = _matrix[i][j];                 vvParentpath[i][j] = i;             }             else             {                 // 如果两顶点之间不可达，前驱节点为-1                 vvParentpath[i][j] = -1;             }         }     }      // 这里是核心部分，遍历所有顶点作为中间顶点，以检查是否存在更短路径     for (size_t k = 0; k < _vertex.size(); k++)     {         for (size_t i = 0; i < _vertex.size(); i++)         {             for (size_t j = 0; j < _vertex.size(); j++)             {                 // 如果存在通过顶点k作为中间顶点的更短路径，则更新距离和前驱节点                 if (vvDest[i][k] != MAX_W && vvDest[k][j] != MAX_W && vvDest[i][k] + vvDest[k][j] < vvDest[i][j])                 {                     vvDest[i][j] = vvDest[i][k] + vvDest[k][j];                     vvParentpath[i][j] = vvParentpath[k][j];                 }             }         }          // 打印每次迭代后的距离矩阵和前驱节点矩阵（可选）         				//打印权值和路径矩阵观察数据 				//cout << "     "; 				//for (size_t i = 0; i < _vertex.size(); i++) 				//{ 				//	cout << _vertex[i] << " "; 				//} 				//cout << endl;  				for (size_t i = 0; i < _vertex.size(); ++i) 				{ 					cout << _vertex[i] << " "; 					for (size_t j = 0; j < _vertex.size(); ++j) 					{ 						if (vvDest[i][j] == MAX_W) 						{ 							//cout << "*" << " "; 							printf("%3c", '*'); 						} 						else 						{ 							//cout << vvDest[i][j] << " "; 							printf("%3d", vvDest[i][j]); 						} 					} 					cout << endl; 				}  				cout << endl; 				for (size_t i = 0; i < _vertex.size(); ++i) 				{ 					for (size_t j = 0; j < _vertex.size(); ++j) 					{ 						//cout << vvParentPath[i][j] << " "; 						printf("%3d", vvParentpath[i][j]); 					} 					cout << endl; 				} 				cout << "=================================" << endl; 			}     } } 

我们构建这样的图：

	void TestFloydWarshall() 	{ 		const char* str = "12345"; 		Graph<char, int, INT_MAX, true> g(str, strlen(str)); 		g.AddEdge('1', '2', 3); 		g.AddEdge('1', '3', 8); 		g.AddEdge('1', '5', -4); 		g.AddEdge('2', '4', 1); 		g.AddEdge('2', '5', 7); 		g.AddEdge('3', '2', 4); 		g.AddEdge('4', '1', 2); 		g.AddEdge('4', '3', -5); 		g.AddEdge('5', '4', 6); 		vector<vector<int>> vvDist; 		vector<vector<int>> vvParentPath; 		g.FloydWarshall(vvDist, vvParentPath); 	} 

大家可以对应一下上面的图，这里注意一下，我们的路径的数组存储的是下标，所以每组的第二个图比上图中的数值小1，这是正常的。

我们可以把每个结点到其他结点的最短路径打印出来：

	void TestFloydWarshall() 	{ 		const char* str = "12345"; 		Graph<char, int, INT_MAX, true> g(str, strlen(str)); 		g.AddEdge('1', '2', 3); 		g.AddEdge('1', '3', 8); 		g.AddEdge('1', '5', -4); 		g.AddEdge('2', '4', 1); 		g.AddEdge('2', '5', 7); 		g.AddEdge('3', '2', 4); 		g.AddEdge('4', '1', 2); 		g.AddEdge('4', '3', -5); 		g.AddEdge('5', '4', 6); 		vector<vector<int>> vvDist; 		vector<vector<int>> vvParentPath; 		g.FloydWarshall(vvDist, vvParentPath); 		// 打印任意两点之间的最短路径 		for (size_t i = 0; i < strlen(str); ++i) 		{ 			g.PrintShortestPath(str[i], vvDist[i], vvParentPath[i]); 			cout << endl; 		} 	} 

我们也可以把之前小潮的图拿出来测测：

三种最短路径算法比较

在图论中，寻找最短路径是常见的问题，有多种算法可以解决这个问题，包括Dijkstra算法、Bellman-Ford算法和Floyd-Warshall算法。下面是对这三种算法的比较：

1. Dijkstra算法

适用场景：适用于没有负权边的加权图，无论是有向还是无向图。

优点：

• 时间复杂度较低，使用优先队列优化后的时间复杂度为O((V+E)logV)。
• 算法简单，易于理解和实现。

缺点：

• 不能处理含有负权边的图。

2. Bellman-Ford算法

适用场景：适用于任何加权图，包括含有负权边的图，但不能有负权回路。

优点：

• 可以检测并报告图中是否存在负权回路。
• 对于稀疏图，性能优于Floyd-Warshall算法。

缺点：

• 时间复杂度较高，为O(VE)，当E较大时效率低。
• 每次迭代都需要更新所有边，即使某些边的最短路径已经确定。

3. Floyd-Warshall算法

适用场景：适用于任何加权图，包括含有负权边的图，但不能有负权回路。特别适合于求解所有顶点对之间的最短路径问题。

优点：

• 可以一次计算出所有顶点对的最短路径。
• 算法简洁，易于理解。

缺点：

• 时间复杂度高，为O(V^3)，对于大规模图的计算效率低下。
• 需要额外的空间来存储中间结果，空间复杂度为O(V^2)。

总结

• 如果只需要求解单源最短路径问题，且图中没有负权边，Dijkstra算法是首选。
• 如果图中可能含有负权边，但没有负权回路，Bellman-Ford算法更为适用。
• 当需要求解所有顶点对之间的最短路径时，Floyd-Warshall算法是最直接的选择，尽管它的时间和空间复杂度较高。

选择哪种算法取决于具体的问题背景和图的特性。