【C++从0到王者】第四十八站：最短路径

文章目录

  • 一、最短路径
  • 二、单源最短路径 -- Dijkstra算法
    • 1.单源最短路径问题
    • 2.算法思想
    • 3.代码实现
    • 4.负权值带来的问题
  • 三、单源最短路径 -- Bellman-Ford算法
    • 1.算法思想
    • 2.算法实现
    • 3.SPFA优化
    • 4.负权回路
  • 四、多源最短路径 -- Floyd-Warshall算法
    • 1.算法思想
    • 2.算法实现

一、最短路径

最短路径问题：从在带权有向图G中的某一顶点出发，找出一条通往另一顶点的最短路径，最短也就是沿路径各边的权值总和达到最小。

一般来说，最短路径都是针对于有向图的，但是对于无向图也是可以的！

二、单源最短路径 – Dijkstra算法

1.单源最短路径问题

单源最短路径问题：给定一个图G = ( V ， E ) ，求源结点s ∈ V到图中每个结点v ∈ V的最短路径。Dijkstra算法就适用于解决带权重的有向图上的单源最短路径问题，同时算法要求图中所有边的权重非负。一般在求解最短路径的时候都是已知一个起点和一个终点，所以使用Dijkstra算法求解过后也就得到了所需起点到终点的最短路径。

2.算法思想

针对一个带权有向图G，将所有结点分为两组S和Q，S是已经确定最短路径的结点集合，在初始时为空（初始时就可以将源节点s放入，毕竟源节点到自己的代价是0），Q 为其余未确定最短路径的结点集合，每次从Q 中找出一个起点到该结点代价最小的结点u ，将u 从Q 中移出，并放入S中，对u 的每一个相邻结点v进行松弛操作。松弛即对每一个相邻结点v ，判断源节点s到结点u的代价与u 到v 的代价之和是否比原来s 到v 的代价更小，若代价比原来小则要将s 到v 的代价更新为s 到u 与u 到v 的代价之和，否则维持原样。如此一直循环直至集合Q 为空，即所有节点都已经查找过一遍并确定了最短路径，至于一些起点到达不了的结点在算法循环后其代价仍为初始设定的值，不发生变化。Dijkstra算法每次都是选择V-S中最小的路径节点来进行更新，并加入S中，所以该算法使用的是贪心策略

注意:Dijkstra算法存在的问题是不支持图中带负权路径，如果带有负权路径，则可能会找不到一些路径的最短路径。

image-20240222011135364

3.代码实现

namespace matrix
{
	//V代表顶点， W是weight代表权值，MAX_W代表权值的最大值，Direction代表是有向图还是无向图,flase表示无向
	template<class V, class W, W Max_W = INT_MAX, bool Direction = false>
	class Graph
	{
		typedef Graph<V, W, Max_W, Direction> Self;
	public:
		Graph() = default;
		//图的创建
		//1. IO输入 不方便测试
		//2. 图结构关系写到文件，读取文件
		//3. 手动添加边
		Graph(const V* a, size_t n)
		{
			_vertexs.reserve(n);
			for (size_t i = 0; i < n; i++)
			{
				_vertexs.push_back(a[i]);
				_indexMap[a[i]] = i;
			}
			_matrix.resize(n);
			for (size_t i = 0; i < _matrix.size(); i++)
			{
				_matrix[i].resize(n, Max_W);
			}
		}
		size_t GetVertexIndex(const V& v)
		{
			//return _indexMap[v];
			auto it = _indexMap.find(v);
			if (it != _indexMap.end())
			{
				return it->second;
			}
			else
			{
				//assert(false)
				throw invalid_argument("顶点不存在");
				return -1;
			}
		}
		void _AddEdge(size_t srci, size_t dsti, const W& w)
		{
			_matrix[srci][dsti] = w;
			if (Direction == false)
			{
				_matrix[dsti][srci] = w;
			}
		}
		void AddEdge(const V& src, const V& dst, const W& w)
		{
			size_t srci = GetVertexIndex(src);
			size_t dsti = GetVertexIndex(dst);
			_AddEdge(srci, dsti, w);
		}
		void Print()
		{
			for (size_t i = 0; i < _vertexs.size(); i++)
			{
				cout << "[" << i << "]" << "->" << _vertexs[i] << endl;
			}
			cout << endl;

			cout << "   ";
			for (int i = 0; i < _vertexs.size(); i++)
			{
				//cout << _vertexs[i] << " ";
				printf("%-3d ", i);
			}
			cout << endl;
			for (size_t i = 0; i < _matrix.size(); i++)
			{
				//cout << _vertexs[i] << " ";
				printf("%d ", i);
				for (size_t j = 0; j < _matrix[i].size(); j++)
				{
					if (_matrix[i][j] == INT_MAX)
					{
						cout << " *  ";
					}
					else
					{
						printf(" %d  ", _matrix[i][j]);
						//cout << _matrix[i][j] << " ";
					}
				}
				cout << endl;
			}
			for (size_t i = 0; i < _matrix.size(); i++)
			{
				for (size_t j = 0; j < _matrix[i].size(); j++)
				{
					if (i < j && _matrix[i][j] != Max_W)
					{
						cout << _vertexs[i] << "->" << _vertexs[j] << ":" << _matrix[i][j] << endl;
					}
				}
			}
		}

		void BFS(const V& src)
		{
			int srci = GetVertexIndex(src);
			queue<int> q; //广度遍历的队列
			vector<bool> visited(_vertexs.size(), false); //标记数组
			q.push(srci); //起点入队
			visited[srci] = true; //已经被遍历过了
			while (!q.empty())
			{
				int front = q.front();
				q.pop();
				cout << front << ":" << _vertexs[front] << endl;
				//把front顶点的邻接顶点入队列
				for (size_t i = 0; i < _matrix[front].size(); i++)
				{
					if (_matrix[front][i] != Max_W)
					{
						if (visited[i] == false)
						{
							q.push(i);
							visited[i] = true;
						}
					}
				}
			}
		} 

		void BFSLevel(const V& src)
		{
			int srci = GetVertexIndex(src);
			queue<int> q; //广度遍历的队列
			vector<bool> visited(_vertexs.size(), false); //标记数组
			q.push(srci); //起点入队
			visited[srci] = true; //已经被遍历过了
			int levelSize = 1;
			while (!q.empty())
			{
				for (int i = 0; i < levelSize; i++)
				{
					int front = q.front();
					q.pop();
					cout << front << ":" << _vertexs[front] << " ";
					//把front顶点的邻接顶点入队列
					for (size_t i = 0; i < _matrix[front].size(); i++)
					{
						if (_matrix[front][i] != Max_W)
						{
							if (visited[i] == false)
							{
								q.push(i);
								visited[i] = true;
							}
						}
					}
				}
				cout << endl;
				levelSize = q.size();
			}
		}
		void _DFS(size_t srci, vector<bool>& visited)
		{
			cout << srci << ":" << _vertexs[srci] << endl;
			visited[srci] = true;
			for (int i = 0; i < _matrix[srci].size(); i++)
			{
				if (_matrix[srci][i] != Max_W && visited[i] == false)
				{
					_DFS(i, visited);
				}
			}
		}
		void DFS(const V& src)
		{
			int srci = GetVertexIndex(src);
			vector<bool> visited(_vertexs.size(), false);
			_DFS(srci, visited);
		}

		struct Edge
		{
			int _srci;
			int _dsti;
			W _w;
			Edge(int srci, int dsti, W w)
				:_srci(srci)
				,_dsti(dsti)
				,_w(w)
			{}
			bool operator>(const Edge& e) const
			{
				return this->_w > e._w;
			}
		};

		//传入的是一个只有结点的，没有边的图
		W Kruskal(Self& minTree)
		{
			//先将所有的边，按照小堆的方式进行组织起来
			priority_queue<Edge, vector<Edge>, greater<Edge>> minque;
		   	size_t n = _vertexs.size();
			for (int i = 0; i < n; i++)
			{
				for (int j = 0; j < n; j++)
				{
					//由于这里是无向图，他是一个对称矩阵，但是我们的边只考虑一半就已经可以了。剩下的就重复了。
					if (i < j && _matrix[i][j] != Max_W)
					{
						//已经按照自身的，带有边的图，将所有的边的信息全部组织好了
						minque.push(Edge(i, j, _matrix[i][j]));
					}
				}
			}
			//因为最小生成树一定是n-1条边，所以我们现在要选出n-1条边，size是计数器
			int size = 0;
			//用于计算权值
			W totalW = W();
			//最关键的问题是判环，这里我们可以用并查集去检测是否这两个顶点在一个集合里面，如果在集合里面，说明一定是连通的，在加上就成环了
			UnionFindSet ufs(n);
			//开始选边，我们要考虑到所有的边
			while (!minque.empty())
			{
				//取出一个最小的边，然后就可以将他踢出优先级队列了，如果被选中不需要它了，如果没有被选中，那只能是因为出现环了才不要它了。
				Edge min = minque.top();
				minque.pop();
				//看看是否在一个集合里面，如果在一个集合里面，那么他们已经是连通了，没必要在连通，还想要连通那么一定是环！
				if (!ufs.InSet(min._srci, min._dsti))
				{
					//我们可以看看我们选出来的边
					cout << _vertexs[min._srci] << "-" << _vertexs[min._dsti] << ":" << min._w << endl;
					//该边是符合的，我们直接为这个图加上边
					minTree._AddEdge(min._srci, min._dsti, min._w);
					//加上之后，就连通了，我们让他们形成集合
					ufs.Union(min._srci, min._dsti);
					//我们一定只有n-1条边，我们需要计数
					++size;
					//将总的权值要加起来
					totalW += min._w;
				}
				//成环的情况，我们只是看看这是哪条边
				else
				{
					cout << "构成环啦！:";
					cout << _vertexs[min._srci] << "-" << _vertexs[min._dsti] << ":" << min._w << endl;
				}
			}
			//上面的循环中，如果图是连通的，那么最终一定选出来的是n-1条边。除非图是不连通的。
			if (size == n - 1)
			{
				return totalW;
			}
			//图不连通，直接返回0
			else
			{
				return W();
			}
		}


		W Prim(Self& minTree, const V& src)
		{
			size_t srci = GetVertexIndex(src);
			int n = _vertexs.size();
			//使用集合的方式
			//set<int> X;
			//set<int> Y;
			//X.insert(srci);
			//for (int i = 0; i < n; i++)
			//{
			//	if (i != srci)
			//	{
			//		Y.insert(i);
			//	}
			//}

			//利用vector的方式,去记录两个集合。
			vector<bool> X(n, false);
			vector<bool> Y(n, true);
			X[srci] = true;
			Y[srci] = false;

			//从X->Y集合中连接的边去选最小的边
			priority_queue<Edge, vector<Edge>, greater<Edge>> minq;
			//把目前为止X集合（仅仅只有起点）的相关的边，全部放入优先级队列中
			for (int i = 0; i < n; i++)
			{
				if (_matrix[srci][i] != Max_W)
				{
					minq.push(Edge(srci, i, _matrix[srci][i]));
				}
			}
			//size用来判断是否达到最小生成树的个数n-1,totalW用来计算权值之和
			size_t size = 0;
			W totalW = W();
			//我们开始在优先级队列中去寻找
			while (!minq.empty())
			{
				//在优先级队列中找到一个最小的元素，由于优先级队列中的一定是我们X集合可以延申的边。所以是满足Prim的选边条件的
				Edge min = minq.top();
				//如果边使用了，那么就不用了，如果不使用，那肯定是因为环才导致的，那也不要了
				minq.pop();
				//这里比较巧妙，因为根据我们的算法思想，我们选边的时候一定是从X集合的某一个顶点开始的，然后去找一个不在X集合里面的顶点
				//所以这里我们可以直接判断目的点是否在X集合里面，如果在，那么一定是环。如果不是，才可以把这条边给加上去
				if (X[min._dsti])
				{
					//cout << "构成环：";
					//cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl;
					continue;
				}

				//把边给加上去
				minTree._AddEdge(min._srci, min._dsti, min._w);
				//cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl;
				
				//X.insert(min._dsti);
				//Y.erase(min._dsti);
				
				//处理一下目的点的边
				X[min._dsti] = true;
				Y[min._dsti] = false;

				++size;
				totalW += min._w;
				//这里相当于一次优化，因为该循环一定可以保证选出来的n-1条边是最小生成树，
				//后面的优先级队列中的任何一条边一定会导致出现环，会在前面的检测目的点是否在X集合中被处理掉。
				//这里则是直接不用继续入其他的边进入队列了。可以提高一些效率，减少无用的操作
				if (size == n - 1)
				{
					break;
				}
				//当一条边添加完成后，它就属于X集合了，我们可以将该点所延申出的边给加入到优先级队列中
				//只有该边存在，且目的地没有被加入过的时候，才会入队列。值得耐人寻味的是，这里虽然已经处理过一次可能出现环的情况了
				//但是可能由于在添加边的时候，导致某些优先级队列中的边会导致构成环了，所以就有了前面的再次根据目的地时候在X集合中去判环
				for (int i = 0; i < n; i++)
				{
					if (_matrix[min._dsti][i] != Max_W && X[i] == false)
					{
						minq.push(Edge(min._dsti, i, _matrix[min._dsti][i]));
					}
				}
			}
			if (size == n - 1)
			{
				return totalW;
			}
			else
			{
				return W();
			}
		}

		void PrintShortPath(const V& src, const vector<W>& dist, const vector<int>& pPath)
		{
			size_t srci = GetVertexIndex(src);
			int n = _vertexs.size();
			for (int i = 0; i < n; i++)
			{
				if (i != srci)
				{
					cout << "[" << "pathlenth:" << dist[i] << "]";
					stack<int> path;
					size_t parent = i;
					while (parent != srci)
					{
						path.push(parent);
						parent = pPath[parent];
					}
					path.push(parent);
					cout << "path:";
					while (!path.empty())
					{ 
						int top = path.top();
						path.pop();
						cout << _vertexs[top] << "->";
					}
					cout << "nullptr" << endl;

				}
			}

		}
		//src是起始结点，dist数组的内容是存放最短路径值的权值，即每个元素的内容代表着从起始结点到该结点的最短路径
		//pPath数组是路径的数组，因为有时候我们需要求出路径的具体走法，所以我们可以用数组的方式，类似于并查集去寻找路径的方式，建立一颗树
		void Dijkstra(const V& src, vector<W>& dist, vector<int>& pPath)
		{
			//确定好起始结点的下标
			size_t srci = GetVertexIndex(src);
			int n = _vertexs.size();
			//我们先让所有的最短路径无穷。即还未求出来
			dist.resize(n, Max_W);
			//注意源节点到源节点的最短路径一定是0
			dist[srci] = 0;
			//我们让所有的路径都设置为-1，意味着所有的结点都没有找出来最短路径
			pPath.resize(n, -1);
			//这是表示起点它的路径就是它自己，这步其实只是为了让起点和为求出最短路径给分开表示。不然都用-1可能会混乱
			pPath[srci] = srci;
			//这个S集合代表我们已经求出最短路径的集合。如果是true代表着这个结点早已求出了最短路径。false代表未求出
			vector<bool> S(n, false);
			//注意这里我们做一下特殊处理，虽然我们起点它本来就应该放在这个集合里面，但是我们还是先让它为false。这里我们其实是想与下面的循环进行合并
			//所以迫不得已做的操作，因为一旦将某个结点设置为true，那么它的相邻的结点路径也应该被更新一下，那么这里就要把下面的对于代码拷贝一份。
			//所以为了让代码简洁，我们直接不写这一步了，和下面的进行合并
			//S[srci] = true;

			//这里只是控制一下循环次数，因为我们要求所有的结点都要被遍历一下，而每次只会遍历一个结点，即将一个结点给放入S集合。
			//我们每次点亮的一定是之前从未遍历过的结点
			for(int j = 0; j < n; j++)
			{
				//Dijkstra算法要求每次都要找出一个，还没有被访问过的（不在S集合的），并且是有路径的，且路径是当前最小的一个结点
				//对于第一次找到的就是srci以及所对应的0值
				int u = 0;
				W min = Max_W;
				for (int i = 0; i < n; i++)
				{
					if (S[i] == false && dist[i] < min)
					{
						u = i;
						min = dist[i];
					}
				}
				//找到以后，我们可以让他加入S集合，代表它已经被访问过了。借助这里找到了srci，并且使他加入到S集合
				S[u] = true;
				//松弛更新u连接顶点v， srci->u + u->v < srci->v 就更新
				//注意，这里我们需要的是找到我们新加入S集合的邻接的顶点，然后判断是不是需要更新最短路径，
				//但是我们一开始并不知道，所以我们遍历所有的结点，依次判断条件是否满足
				for (int v = 0; v < n; v++)
				{
						//我们这个要更新的不能是我们之前已经访问过的了。因为之前访问过的一定是最短路径了！
					if (S[v] == false &&
						//因为是要邻接的顶点，它必须要直接连通的两个顶点。所以用这个条件进行排除
						_matrix[u][v] != Max_W
						//这是为了看一看用这个算出来的是不是小于我们原来的路径，如果是，那么最短路径就变成它了
						&& dist[u] + _matrix[u][v] < dist[v])
					{
						//更新最短路径
						dist[v] = dist[u] + _matrix[u][v];
						//更新路径的树
						pPath[v] = u;
					}
				}
			}
		}


	private:
		vector<V> _vertexs; //顶点集合
		map<V, int> _indexMap; //顶点对应的下标关系
		vector<vector<W>> _matrix; //临界矩阵
	};
	void TestGraphDijkstra()
	{
		const char* str = "syztx";
		Graph<char, int, INT_MAX, true> g(str, strlen(str));
		g.AddEdge('s', 't', 10);
		g.AddEdge('s', 'y', 5);
		g.AddEdge('y', 't', 3);
		g.AddEdge('y', 'x', 9);
		g.AddEdge('y', 'z', 2);
		g.AddEdge('z', 's', 7);
		g.AddEdge('z', 'x', 6);
		g.AddEdge('t', 'y', 2);
		g.AddEdge('t', 'x', 1);
		g.AddEdge('x', 'z', 4);
		vector<int> dist;
		vector<int> parentPath;
		g.Dijkstra('s', dist, parentPath);
		g.PrintShortPath('s', dist, parentPath);
	}



	void TestGraph()
	{
		Graph<char, int, INT_MAX, true> g("0123", 4);
		g.AddEdge('0', '1', 1);
		g.AddEdge('0', '3', 4);
		g.AddEdge('1', '3', 2);
		g.AddEdge('1', '2', 9);
		g.AddEdge('2', '3', 8);
		g.AddEdge('2', '1', 5);
		g.AddEdge('2', '0', 3);
		g.AddEdge('3', '2', 6);
		g.Print();
	}
	void TestGraphBDFS()
	{
		string a[] = { "张三", "李四", "王五", "赵六", "周七" };
		Graph<string, int> g1(a, sizeof(a) / sizeof(string));
		g1.AddEdge("张三", "李四", 100);
		g1.AddEdge("张三", "王五", 200);
		g1.AddEdge("王五", "赵六", 30);
		g1.AddEdge("王五", "周七", 30);
		g1.Print();
		g1.BFS("张三");
		cout << endl;
		g1.BFSLevel("张三");
		cout << endl;
		g1.DFS("张三");
	}
	void TestGraphMinTree()
	{
		const char* str = "abcdefghi";
		Graph<char, int> g(str, strlen(str));
		g.AddEdge('a', 'b', 4);
		g.AddEdge('a', 'h', 8);
		//g.AddEdge('a', 'h', 9);
		g.AddEdge('b', 'c', 8);
		g.AddEdge('b', 'h', 11); 
		g.AddEdge('c', 'i', 2);
		g.AddEdge('c', 'f', 4);
		g.AddEdge('c', 'd', 7);
		g.AddEdge('d', 'f', 14);
		g.AddEdge('d', 'e', 9);
		g.AddEdge('e', 'f', 10);
		g.AddEdge('f', 'g', 2);
		g.AddEdge('g', 'h', 1);
		g.AddEdge('g', 'i', 6);
		g.AddEdge('h', 'i', 7);
		//Graph<char, int> kminTree;
		//Graph<char, int> kminTree(str, strlen(str));
		//cout << "Kruskal:" << g.Kruskal(kminTree) << endl;
		//kminTree.Print();
		//Graph<char, int> pminTree(str, strlen(str));
		//cout << "Prim:" << g.Prim(pminTree, 'a') << endl;
		//pminTree.Print();

		for (int i = 0; i < strlen(str); i++)
		{
			Graph<char, int> pminTree(str, strlen(str));
			cout << "Prim:" << str[i] << ":" << g.Prim(pminTree, str[i]) << endl;
		}


	}
}

运行结果如下

image-20240222013452523

上面的算法具体解释已经放在了注释当中,我们将代码单独拉出来方便我们阅读

注意的是,已经访问过的结点,一定不能再次访问了!

		//src是起始结点，dist数组的内容是存放最短路径值的权值，即每个元素的内容代表着从起始结点到该结点的最短路径
		//pPath数组是路径的数组，因为有时候我们需要求出路径的具体走法，所以我们可以用数组的方式，类似于并查集去寻找路径的方式，建立一颗树
		void Dijkstra(const V& src, vector<W>& dist, vector<int>& pPath)
		{
			//确定好起始结点的下标
			size_t srci = GetVertexIndex(src);
			int n = _vertexs.size();
			//我们先让所有的最短路径无穷。即还未求出来
			dist.resize(n, Max_W);
			//注意源节点到源节点的最短路径一定是0
			dist[srci] = 0;
			//我们让所有的路径都设置为-1，意味着所有的结点都没有找出来最短路径
			pPath.resize(n, -1);
			//这是表示起点它的路径就是它自己，这步其实只是为了让起点和为求出最短路径给分开表示。不然都用-1可能会混乱
			pPath[srci] = srci;
			//这个S集合代表我们已经求出最短路径的集合。如果是true代表着这个结点早已求出了最短路径。false代表未求出
			vector<bool> S(n, false);
			//注意这里我们做一下特殊处理，虽然我们起点它本来就应该放在这个集合里面，但是我们还是先让它为false。这里我们其实是想与下面的循环进行合并
			//所以迫不得已做的操作，因为一旦将某个结点设置为true，那么它的相邻的结点路径也应该被更新一下，那么这里就要把下面的对于代码拷贝一份。
			//所以为了让代码简洁，我们直接不写这一步了，和下面的进行合并
			//S[srci] = true;

			//这里只是控制一下循环次数，因为我们要求所有的结点都要被遍历一下，而每次只会遍历一个结点，即将一个结点给放入S集合。
			//我们每次点亮的一定是之前从未遍历过的结点
			for(int j = 0; j < n; j++)
			{
				//Dijkstra算法要求每次都要找出一个，还没有被访问过的（不在S集合的），并且是有路径的，且路径是当前最小的一个结点
				//对于第一次找到的就是srci以及所对应的0值
				int u = 0;
				W min = Max_W;
				for (int i = 0; i < n; i++)
				{
					if (S[i] == false && dist[i] < min)
					{
						u = i;
						min = dist[i];
					}
				}
				//找到以后，我们可以让他加入S集合，代表它已经被访问过了。借助这里找到了srci，并且使他加入到S集合
				S[u] = true;
				//松弛更新u连接顶点v， srci->u + u->v < srci->v 就更新
				//注意，这里我们需要的是找到我们新加入S集合的邻接的顶点，然后判断是不是需要更新最短路径，
				//但是我们一开始并不知道，所以我们遍历所有的结点，依次判断条件是否满足
				for (int v = 0; v < n; v++)
				{
						//我们这个要更新的不能是我们之前已经访问过的了。因为之前访问过的一定是最短路径了！
					if (S[v] == false &&
						//因为是要邻接的顶点，它必须要直接连通的两个顶点。所以用这个条件进行排除
						_matrix[u][v] != Max_W
						//这是为了看一看用这个算出来的是不是小于我们原来的路径，如果是，那么最短路径就变成它了
						&& dist[u] + _matrix[u][v] < dist[v])
					{
						//更新最短路径
						dist[v] = dist[u] + _matrix[u][v];
						//更新路径的树
						pPath[v] = u;
					}
				}
			}
		}

4.负权值带来的问题

我们看一下下面的测试用例

对于下面的图

image-20240222013946282

	void TestGraphDijkstra()
	{
		const char* str = "sytx";
		Graph<char, int, INT_MAX, true> g(str, strlen(str));
		g.AddEdge('s', 't', 10);
		g.AddEdge('s', 'y', 5);
		g.AddEdge('t', 'y', -7);
		g.AddEdge('y', 'x', 3);
		vector<int> dist;
		vector<int> parentPath;
		g.Dijkstra('s', dist, parentPath);
		g.PrintShortPath('s', dist, parentPath);
	}

我们的运行结果为

image-20240222014018356

其实我们可以很容易的发现,第一条路径和第三条路径的最短距离,直接从图中去看的话应该是3和6才对,但是结果居然是5和8.

它的具体步骤如下

image-20240222014504325

所以它的最终是出现了问题

Dijkstra算法无法解决负权值问题主要有两个原因：

  1. Dijkstra算法的基本思想是贪心算法，它总是选择当前距离起始点最近（或说权重最小）的顶点进行处理。如果图中存在负权重的边，那么已经确定最短路径的顶点的最短路径可能会因为这个负权重的边而改变，这与Dijkstra算法“确定的最短路径就是永久不变的”初衷相矛盾。
  2. 如果图中存在负权重的环路，Dijkstra算法可能会陷入无限循环中，因为每次经过这个负权重的环，都能使得路径的权值变小。

因此，如果图中边的权值存在负值，我们通常使用Bellman-Ford算法或者Floyd-Warshall算法，这些算法能正确处理负权值的情况。

这个算法的时间复杂度是O(N²)，空间复杂度是O(N)

三、单源最短路径 – Bellman-Ford算法

1.算法思想

Dijkstra算法只能用来解决正权图的单源最短路径问题，但有些题目会出现负权图。这时这个算法就不能帮助我们解决问题了，而bellman—ford算法可以解决负权图的单源最短路径问题。它的优点是可以解决有负权边的单源最短路径问题，而且可以用来判断是否有负权回路。它也有明显的缺点，它的时间复杂度 O(N*E) (N是点数，E是边数)普遍是要高于Dijkstra算法O(N²)的。像这里如果我们使用邻接矩阵实现，那么遍历所有边的数量的时间复杂度就是O(N^3)，这里也可以看出来Bellman-Ford就是一种暴力求解更新

image-20240224125506279

2.算法实现

如下代码所示

namespace matrix
{
	//V代表顶点， W是weight代表权值，MAX_W代表权值的最大值，Direction代表是有向图还是无向图,flase表示无向
	template<class V, class W, W Max_W = INT_MAX, bool Direction = false>
	class Graph
	{
		typedef Graph<V, W, Max_W, Direction> Self;
	public:
		Graph() = default;
		//图的创建
		//1. IO输入 不方便测试
		//2. 图结构关系写到文件，读取文件
		//3. 手动添加边
		Graph(const V* a, size_t n)
		{
			_vertexs.reserve(n);
			for (size_t i = 0; i < n; i++)
			{
				_vertexs.push_back(a[i]);
				_indexMap[a[i]] = i;
			}
			_matrix.resize(n);
			for (size_t i = 0; i < _matrix.size(); i++)
			{
				_matrix[i].resize(n, Max_W);
			}
		}
		size_t GetVertexIndex(const V& v)
		{
			//return _indexMap[v];
			auto it = _indexMap.find(v);
			if (it != _indexMap.end())
			{
				return it->second;
			}
			else
			{
				//assert(false)
				throw invalid_argument("顶点不存在");
				return -1;
			}
		}
		void _AddEdge(size_t srci, size_t dsti, const W& w)
		{
			_matrix[srci][dsti] = w;
			if (Direction == false)
			{
				_matrix[dsti][srci] = w;
			}
		}
		void AddEdge(const V& src, const V& dst, const W& w)
		{
			size_t srci = GetVertexIndex(src);
			size_t dsti = GetVertexIndex(dst);
			_AddEdge(srci, dsti, w);
		}
		void Print()
		{
			for (size_t i = 0; i < _vertexs.size(); i++)
			{
				cout << "[" << i << "]" << "->" << _vertexs[i] << endl;
			}
			cout << endl;

			cout << "   ";
			for (int i = 0; i < _vertexs.size(); i++)
			{
				//cout << _vertexs[i] << " ";
				printf("%-3d ", i);
			}
			cout << endl;
			for (size_t i = 0; i < _matrix.size(); i++)
			{
				//cout << _vertexs[i] << " ";
				printf("%d ", i);
				for (size_t j = 0; j < _matrix[i].size(); j++)
				{
					if (_matrix[i][j] == INT_MAX)
					{
						cout << " *  ";
					}
					else
					{
						printf(" %d  ", _matrix[i][j]);
						//cout << _matrix[i][j] << " ";
					}
				}
				cout << endl;
			}
			for (size_t i = 0; i < _matrix.size(); i++)
			{
				for (size_t j = 0; j < _matrix[i].size(); j++)
				{
					if (i < j && _matrix[i][j] != Max_W)
					{
						cout << _vertexs[i] << "->" << _vertexs[j] << ":" << _matrix[i][j] << endl;
					}
				}
			}
		}

		void BFS(const V& src)
		{
			int srci = GetVertexIndex(src);
			queue<int> q; //广度遍历的队列
			vector<bool> visited(_vertexs.size(), false); //标记数组
			q.push(srci); //起点入队
			visited[srci] = true; //已经被遍历过了
			while (!q.empty())
			{
				int front = q.front();
				q.pop();
				cout << front << ":" << _vertexs[front] << endl;
				//把front顶点的邻接顶点入队列
				for (size_t i = 0; i < _matrix[front].size(); i++)
				{
					if (_matrix[front][i] != Max_W)
					{
						if (visited[i] == false)
						{
							q.push(i);
							visited[i] = true;
						}
					}
				}
			}
		} 

		void BFSLevel(const V& src)
		{
			int srci = GetVertexIndex(src);
			queue<int> q; //广度遍历的队列
			vector<bool> visited(_vertexs.size(), false); //标记数组
			q.push(srci); //起点入队
			visited[srci] = true; //已经被遍历过了
			int levelSize = 1;
			while (!q.empty())
			{
				for (int i = 0; i < levelSize; i++)
				{
					int front = q.front();
					q.pop();
					cout << front << ":" << _vertexs[front] << " ";
					//把front顶点的邻接顶点入队列
					for (size_t i = 0; i < _matrix[front].size(); i++)
					{
						if (_matrix[front][i] != Max_W)
						{
							if (visited[i] == false)
							{
								q.push(i);
								visited[i] = true;
							}
						}
					}
				}
				cout << endl;
				levelSize = q.size();
			}
		}
		void _DFS(size_t srci, vector<bool>& visited)
		{
			cout << srci << ":" << _vertexs[srci] << endl;
			visited[srci] = true;
			for (int i = 0; i < _matrix[srci].size(); i++)
			{
				if (_matrix[srci][i] != Max_W && visited[i] == false)
				{
					_DFS(i, visited);
				}
			}
		}
		void DFS(const V& src)
		{
			int srci = GetVertexIndex(src);
			vector<bool> visited(_vertexs.size(), false);
			_DFS(srci, visited);
		}

		struct Edge
		{
			int _srci;
			int _dsti;
			W _w;
			Edge(int srci, int dsti, W w)
				:_srci(srci)
				,_dsti(dsti)
				,_w(w)
			{}
			bool operator>(const Edge& e) const
			{
				return this->_w > e._w;
			}
		};

		//传入的是一个只有结点的，没有边的图
		W Kruskal(Self& minTree)
		{
			//先将所有的边，按照小堆的方式进行组织起来
			priority_queue<Edge, vector<Edge>, greater<Edge>> minque;
		   	size_t n = _vertexs.size();
			for (int i = 0; i < n; i++)
			{
				for (int j = 0; j < n; j++)
				{
					//由于这里是无向图，他是一个对称矩阵，但是我们的边只考虑一半就已经可以了。剩下的就重复了。
					if (i < j && _matrix[i][j] != Max_W)
					{
						//已经按照自身的，带有边的图，将所有的边的信息全部组织好了
						minque.push(Edge(i, j, _matrix[i][j]));
					}
				}
			}
			//因为最小生成树一定是n-1条边，所以我们现在要选出n-1条边，size是计数器
			int size = 0;
			//用于计算权值
			W totalW = W();
			//最关键的问题是判环，这里我们可以用并查集去检测是否这两个顶点在一个集合里面，如果在集合里面，说明一定是连通的，在加上就成环了
			UnionFindSet ufs(n);
			//开始选边，我们要考虑到所有的边
			while (!minque.empty())
			{
				//取出一个最小的边，然后就可以将他踢出优先级队列了，如果被选中不需要它了，如果没有被选中，那只能是因为出现环了才不要它了。
				Edge min = minque.top();
				minque.pop();
				//看看是否在一个集合里面，如果在一个集合里面，那么他们已经是连通了，没必要在连通，还想要连通那么一定是环！
				if (!ufs.InSet(min._srci, min._dsti))
				{
					//我们可以看看我们选出来的边
					cout << _vertexs[min._srci] << "-" << _vertexs[min._dsti] << ":" << min._w << endl;
					//该边是符合的，我们直接为这个图加上边
					minTree._AddEdge(min._srci, min._dsti, min._w);
					//加上之后，就连通了，我们让他们形成集合
					ufs.Union(min._srci, min._dsti);
					//我们一定只有n-1条边，我们需要计数
					++size;
					//将总的权值要加起来
					totalW += min._w;
				}
				//成环的情况，我们只是看看这是哪条边
				else
				{
					cout << "构成环啦！:";
					cout << _vertexs[min._srci] << "-" << _vertexs[min._dsti] << ":" << min._w << endl;
				}
			}
			//上面的循环中，如果图是连通的，那么最终一定选出来的是n-1条边。除非图是不连通的。
			if (size == n - 1)
			{
				return totalW;
			}
			//图不连通，直接返回0
			else
			{
				return W();
			}
		}


		W Prim(Self& minTree, const V& src)
		{
			size_t srci = GetVertexIndex(src);
			int n = _vertexs.size();
			//使用集合的方式
			//set<int> X;
			//set<int> Y;
			//X.insert(srci);
			//for (int i = 0; i < n; i++)
			//{
			//	if (i != srci)
			//	{
			//		Y.insert(i);
			//	}
			//}

			//利用vector的方式,去记录两个集合。
			vector<bool> X(n, false);
			vector<bool> Y(n, true);
			X[srci] = true;
			Y[srci] = false;

			//从X->Y集合中连接的边去选最小的边
			priority_queue<Edge, vector<Edge>, greater<Edge>> minq;
			//把目前为止X集合（仅仅只有起点）的相关的边，全部放入优先级队列中
			for (int i = 0; i < n; i++)
			{
				if (_matrix[srci][i] != Max_W)
				{
					minq.push(Edge(srci, i, _matrix[srci][i]));
				}
			}
			//size用来判断是否达到最小生成树的个数n-1,totalW用来计算权值之和
			size_t size = 0;
			W totalW = W();
			//我们开始在优先级队列中去寻找
			while (!minq.empty())
			{
				//在优先级队列中找到一个最小的元素，由于优先级队列中的一定是我们X集合可以延申的边。所以是满足Prim的选边条件的
				Edge min = minq.top();
				//如果边使用了，那么就不用了，如果不使用，那肯定是因为环才导致的，那也不要了
				minq.pop();
				//这里比较巧妙，因为根据我们的算法思想，我们选边的时候一定是从X集合的某一个顶点开始的，然后去找一个不在X集合里面的顶点
				//所以这里我们可以直接判断目的点是否在X集合里面，如果在，那么一定是环。如果不是，才可以把这条边给加上去
				if (X[min._dsti])
				{
					//cout << "构成环：";
					//cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl;
					continue;
				}

				//把边给加上去
				minTree._AddEdge(min._srci, min._dsti, min._w);
				//cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl;
				
				//X.insert(min._dsti);
				//Y.erase(min._dsti);
				
				//处理一下目的点的边
				X[min._dsti] = true;
				Y[min._dsti] = false;

				++size;
				totalW += min._w;
				//这里相当于一次优化，因为该循环一定可以保证选出来的n-1条边是最小生成树，
				//后面的优先级队列中的任何一条边一定会导致出现环，会在前面的检测目的点是否在X集合中被处理掉。
				//这里则是直接不用继续入其他的边进入队列了。可以提高一些效率，减少无用的操作
				if (size == n - 1)
				{
					break;
				}
				//当一条边添加完成后，它就属于X集合了，我们可以将该点所延申出的边给加入到优先级队列中
				//只有该边存在，且目的地没有被加入过的时候，才会入队列。值得耐人寻味的是，这里虽然已经处理过一次可能出现环的情况了
				//但是可能由于在添加边的时候，导致某些优先级队列中的边会导致构成环了，所以就有了前面的再次根据目的地时候在X集合中去判环
				for (int i = 0; i < n; i++)
				{
					if (_matrix[min._dsti][i] != Max_W && X[i] == false)
					{
						minq.push(Edge(min._dsti, i, _matrix[min._dsti][i]));
					}
				}
			}
			if (size == n - 1)
			{
				return totalW;
			}
			else
			{
				return W();
			}
		}

		void PrintShortPath(const V& src, const vector<W>& dist, const vector<int>& pPath)
		{
			size_t srci = GetVertexIndex(src);
			int n = _vertexs.size();
			for (int i = 0; i < n; i++)
			{
				if (i != srci)
				{
					cout << "[" << "pathlenth:" << dist[i] << "]";
					stack<int> path;
					size_t parent = i;
					while (parent != srci)
					{
						path.push(parent);
						parent = pPath[parent];
					}
					path.push(parent);
					cout << "path:";
					while (!path.empty())
					{ 
						int top = path.top();
						path.pop();
						cout << _vertexs[top] << "->";
					}
					cout << "nullptr" << endl;

				}
			}

		}
		//src是起始结点，dist数组的内容是存放最短路径值的权值，即每个元素的内容代表着从起始结点到该结点的最短路径
		//pPath数组是路径的数组，因为有时候我们需要求出路径的具体走法，所以我们可以用数组的方式，类似于并查集去寻找路径的方式，建立一颗树
		void Dijkstra(const V& src, vector<W>& dist, vector<int>& pPath)
		{
			//确定好起始结点的下标
			size_t srci = GetVertexIndex(src);
			int n = _vertexs.size();
			//我们先让所有的最短路径无穷。即还未求出来
			dist.resize(n, Max_W);
			//注意源节点到源节点的最短路径一定是0
			dist[srci] = 0;
			//我们让所有的路径都设置为-1，意味着所有的结点都没有找出来最短路径
			pPath.resize(n, -1);
			//这是表示起点它的路径就是它自己，这步其实只是为了让起点和为求出最短路径给分开表示。不然都用-1可能会混乱
			pPath[srci] = srci;
			//这个S集合代表我们已经求出最短路径的集合。如果是true代表着这个结点早已求出了最短路径。false代表未求出
			vector<bool> S(n, false);
			//注意这里我们做一下特殊处理，虽然我们起点它本来就应该放在这个集合里面，但是我们还是先让它为false。这里我们其实是想与下面的循环进行合并
			//所以迫不得已做的操作，因为一旦将某个结点设置为true，那么它的相邻的结点路径也应该被更新一下，那么这里就要把下面的对于代码拷贝一份。
			//所以为了让代码简洁，我们直接不写这一步了，和下面的进行合并
			//S[srci] = true;

			//这里只是控制一下循环次数，因为我们要求所有的结点都要被遍历一下，而每次只会遍历一个结点，即将一个结点给放入S集合。
			//我们每次点亮的一定是之前从未遍历过的结点
			for(int j = 0; j < n; j++)
			{
				//Dijkstra算法要求每次都要找出一个，还没有被访问过的（不在S集合的），并且是有路径的，且路径是当前最小的一个结点
				//对于第一次找到的就是srci以及所对应的0值
				int u = 0;
				W min = Max_W;
				for (int i = 0; i < n; i++)
				{
					if (S[i] == false && dist[i] < min)
					{
						u = i;
						min = dist[i];
					}
				}
				//找到以后，我们可以让他加入S集合，代表它已经被访问过了。借助这里找到了srci，并且使他加入到S集合
				S[u] = true;
				//松弛更新u连接顶点v， srci->u + u->v < srci->v 就更新
				//注意，这里我们需要的是找到我们新加入S集合的邻接的顶点，然后判断是不是需要更新最短路径，
				//但是我们一开始并不知道，所以我们遍历所有的结点，依次判断条件是否满足
				for (int v = 0; v < n; v++)
				{
						//我们这个要更新的不能是我们之前已经访问过的了。因为之前访问过的一定是最短路径了！
					if (S[v] == false &&
						//因为是要邻接的顶点，它必须要直接连通的两个顶点。所以用这个条件进行排除
						_matrix[u][v] != Max_W
						//这是为了看一看用这个算出来的是不是小于我们原来的路径，如果是，那么最短路径就变成它了
						&& dist[u] + _matrix[u][v] < dist[v])
					{
						//更新最短路径
						dist[v] = dist[u] + _matrix[u][v];
						//更新路径的树
						pPath[v] = u;
					}
				}
			}
		}

		bool BellmanFord(const V& src, vector<W>& dist, vector<int>& parentPath)
		{
			size_t n = _vertexs.size();
			size_t srci = GetVertexIndex(src);

			dist.resize(n, Max_W);
			dist[srci] = W();
			parentPath.resize(n, -1);
			parentPath[srci] = srci;
			
			for (int k = 0; k < n; k++)
			{
				bool update = false;
				for (int i = 0; i < n; i++)
				{
					for (int j = 0; j < n; j++)
					{
						update = true;
						//srci->i + i->j => srci->j
						if (_matrix[i][j] != Max_W && dist[i] + _matrix[i][j] < dist[j])
						{
							dist[j] = dist[i] + _matrix[i][j];
							parentPath[j] = i;
						}
					}
				}
				if (update == false)
				{
					break;
				}
			}
			//还能更新就是带有负权回路
			for (int i = 0; i < n; i++)
			{
				for (int j = 0; j < n; j++)
				{
					//srci->i + i->j => srci->j
					if (_matrix[i][j] != Max_W && dist[i] + _matrix[i][j] < dist[j])
					{
						return false;
					}
				}
			}

		}

	private:
		vector<V> _vertexs; //顶点集合
		map<V, int> _indexMap; //顶点对应的下标关系
		vector<vector<W>> _matrix; //临界矩阵
	};

	void TestGraphBellmanFord()
	{
		const char* str = "syztx";
		Graph<char, int, INT_MAX, true> g(str, strlen(str));
		g.AddEdge('s', 't', 6);
		g.AddEdge('s', 'y', 7);
		g.AddEdge('y', 'z', 9);
		g.AddEdge('y', 'x', -3);
		g.AddEdge('z', 's', 2);
		g.AddEdge('z', 'x', 7);
		g.AddEdge('t', 'x', 5);
		g.AddEdge('t', 'y', 8);
		g.AddEdge('t', 'z', -4);
		g.AddEdge('x', 't', -2);
		vector<int> dist;
		vector<int> parentPath;
		if (g.BellmanFord('s', dist, parentPath))
		{
			g.PrintShortPath('s', dist, parentPath);
		}
		else
		{
			cout << "存在负权回路" << endl;
		}
	}


	void TestGraphDijkstra()
	{
		//const char* str = "syztx";
		//Graph<char, int, INT_MAX, true> g(str, strlen(str));
		//g.AddEdge('s', 't', 10);
		//g.AddEdge('s', 'y', 5);
		//g.AddEdge('y', 't', 3);
		//g.AddEdge('y', 'x', 9);
		//g.AddEdge('y', 'z', 2);
		//g.AddEdge('z', 's', 7);
		//g.AddEdge('z', 'x', 6);
		//g.AddEdge('t', 'y', 2);
		//g.AddEdge('t', 'x', 1);
		//g.AddEdge('x', 'z', 4);
		//vector<int> dist;
		//vector<int> parentPath;
		//g.Dijkstra('s', dist, parentPath);
		//g.PrintShortPath('s', dist, parentPath);

		const char* str = "sytx";
		Graph<char, int, INT_MAX, true> g(str, strlen(str));
		g.AddEdge('s', 't', 10);
		g.AddEdge('s', 'y', 5);
		g.AddEdge('t', 'y', -7);
		g.AddEdge('y', 'x', 3);
		vector<int> dist;
		vector<int> parentPath;
		g.Dijkstra('s', dist, parentPath);
		g.PrintShortPath('s', dist, parentPath);

	}



	void TestGraph()
	{
		Graph<char, int, INT_MAX, true> g("0123", 4);
		g.AddEdge('0', '1', 1);
		g.AddEdge('0', '3', 4);
		g.AddEdge('1', '3', 2);
		g.AddEdge('1', '2', 9);
		g.AddEdge('2', '3', 8);
		g.AddEdge('2', '1', 5);
		g.AddEdge('2', '0', 3);
		g.AddEdge('3', '2', 6);
		g.Print();
	}
	void TestGraphBDFS()
	{
		string a[] = { "张三", "李四", "王五", "赵六", "周七" };
		Graph<string, int> g1(a, sizeof(a) / sizeof(string));
		g1.AddEdge("张三", "李四", 100);
		g1.AddEdge("张三", "王五", 200);
		g1.AddEdge("王五", "赵六", 30);
		g1.AddEdge("王五", "周七", 30);
		g1.Print();
		g1.BFS("张三");
		cout << endl;
		g1.BFSLevel("张三");
		cout << endl;
		g1.DFS("张三");
	}
	void TestGraphMinTree()
	{
		const char* str = "abcdefghi";
		Graph<char, int> g(str, strlen(str));
		g.AddEdge('a', 'b', 4);
		g.AddEdge('a', 'h', 8);
		//g.AddEdge('a', 'h', 9);
		g.AddEdge('b', 'c', 8);
		g.AddEdge('b', 'h', 11); 
		g.AddEdge('c', 'i', 2);
		g.AddEdge('c', 'f', 4);
		g.AddEdge('c', 'd', 7);
		g.AddEdge('d', 'f', 14);
		g.AddEdge('d', 'e', 9);
		g.AddEdge('e', 'f', 10);
		g.AddEdge('f', 'g', 2);
		g.AddEdge('g', 'h', 1);
		g.AddEdge('g', 'i', 6);
		g.AddEdge('h', 'i', 7);
		//Graph<char, int> kminTree;
		//Graph<char, int> kminTree(str, strlen(str));
		//cout << "Kruskal:" << g.Kruskal(kminTree) << endl;
		//kminTree.Print();
		//Graph<char, int> pminTree(str, strlen(str));
		//cout << "Prim:" << g.Prim(pminTree, 'a') << endl;
		//pminTree.Print();

		for (int i = 0; i < strlen(str); i++)
		{
			Graph<char, int> pminTree(str, strlen(str));
			cout << "Prim:" << str[i] << ":" << g.Prim(pminTree, str[i]) << endl;
		}


	}
}

Bellman-Ford算法的基本思路是：

  • 首先是遍历所有的边。只要srci->i + i->j的距离小于之前的srci->j的距离。那么就进行更新，同时更新父路径
  • 不过这里可能存在的一个问题是权值和路径对不上的问题，因为只要更新出了更短的一条路径，可能就会影响其他路径。不过我们会发现如果在更新一次的话，那么就会修正这个问题，但是更新路径又会影响其他路径。所以还需要继续更新，最多会更新n轮。最多也就是每个结点都更新一次。
  • 一旦我们发现某一轮没有更新，那么后序的也绝不可能被影响到，所以后面可以不用更新了。

运行结果为

image-20240224143254165

3.SPFA优化

上面代码的时间复杂度是O(N³),我们可以使用SPFA优化

SPFA优化的基本思想是

  • 第一轮更新，所有边入队列
  • 后面的轮次，更新最短路径的边入队列
  • 每次只对队列里面的边进行操作

4.负权回路

如下测试用例所示

	void TestGraphBellmanFord()
	{
		//微调图结构，带有负权回路的测试
		const char* str = "syztx";
		Graph<char, int, INT_MAX, true> g(str, strlen(str));
		g.AddEdge('s', 't', 6);
		g.AddEdge('s', 'y', 7);
		g.AddEdge('y', 'x', -3);
		g.AddEdge('y', 'z', 9);
		g.AddEdge('y', 'x', -3);
		g.AddEdge('y', 's', 1); // 新增
		g.AddEdge('z', 's', 2);
		g.AddEdge('z', 'x', 7);
		g.AddEdge('t', 'x', 5);
		g.AddEdge('t', 'y', -8); // 更改
		g.AddEdge('t', 'z', -4);
		g.AddEdge('x', 't', -2);
		vector<int> dist;
		vector<int> parentPath;
		if (g.BellmanFord('s', dist, parentPath))
		{
		 g.PrintShortPath('s', dist, parentPath);
		}
		else
		{
		 cout << "存在负权回路" << endl;
		}
	}

在这个图中存在负权回路

我们用上面的Bellman-Ford算法可以去检测负权回路，因为最多更新n轮，如果还继续更新，那么只能是负权回路惹的祸。所以可以借此来检测负权回路

运行结果为

image-20240224143600279

注意：

负权回路，神仙难救，求不出最短路径

四、多源最短路径 – Floyd-Warshall算法

1.算法思想

Floyd-Warshall算法是解决任意两点间的最短路径的一种算法。
Floyd算法考虑的是一条最短路径的中间节点，即简单路径p={v1,v2,…,vn}上除v1和vn的任意节点。
设k是p的一个中间节点，那么从i到j的最短路径p就被分成i到k和k到j的两段最短路径p1，p2。p1是从i到k且中间节点属于{1,2，…,k-1}取得的一条最短路径。p2是从k到j且中间节点属于{1，2，…，k-1}取得的一条最短路径。

image-20240224161137658

image-20240224161210688

2.算法实现

namespace matrix
{
	//V代表顶点， W是weight代表权值，MAX_W代表权值的最大值，Direction代表是有向图还是无向图,flase表示无向
	template<class V, class W, W Max_W = INT_MAX, bool Direction = false>
	class Graph
	{
		typedef Graph<V, W, Max_W, Direction> Self;
	public:
		Graph() = default;
		//图的创建
		//1. IO输入 不方便测试
		//2. 图结构关系写到文件，读取文件
		//3. 手动添加边
		Graph(const V* a, size_t n)
		{
			_vertexs.reserve(n);
			for (size_t i = 0; i < n; i++)
			{
				_vertexs.push_back(a[i]);
				_indexMap[a[i]] = i;
			}
			_matrix.resize(n);
			for (size_t i = 0; i < _matrix.size(); i++)
			{
				_matrix[i].resize(n, Max_W);
			}
		}
		size_t GetVertexIndex(const V& v)
		{
			//return _indexMap[v];
			auto it = _indexMap.find(v);
			if (it != _indexMap.end())
			{
				return it->second;
			}
			else
			{
				//assert(false)
				throw invalid_argument("顶点不存在");
				return -1;
			}
		}
		void _AddEdge(size_t srci, size_t dsti, const W& w)
		{
			_matrix[srci][dsti] = w;
			if (Direction == false)
			{
				_matrix[dsti][srci] = w;
			}
		}
		void AddEdge(const V& src, const V& dst, const W& w)
		{
			size_t srci = GetVertexIndex(src);
			size_t dsti = GetVertexIndex(dst);
			_AddEdge(srci, dsti, w);
		}
		void Print()
		{
			for (size_t i = 0; i < _vertexs.size(); i++)
			{
				cout << "[" << i << "]" << "->" << _vertexs[i] << endl;
			}
			cout << endl;

			cout << "   ";
			for (int i = 0; i < _vertexs.size(); i++)
			{
				//cout << _vertexs[i] << " ";
				printf("%-3d ", i);
			}
			cout << endl;
			for (size_t i = 0; i < _matrix.size(); i++)
			{
				//cout << _vertexs[i] << " ";
				printf("%d ", i);
				for (size_t j = 0; j < _matrix[i].size(); j++)
				{
					if (_matrix[i][j] == INT_MAX)
					{
						cout << " *  ";
					}
					else
					{
						printf(" %d  ", _matrix[i][j]);
						//cout << _matrix[i][j] << " ";
					}
				}
				cout << endl;
			}
			for (size_t i = 0; i < _matrix.size(); i++)
			{
				for (size_t j = 0; j < _matrix[i].size(); j++)
				{
					if (i < j && _matrix[i][j] != Max_W)
					{
						cout << _vertexs[i] << "->" << _vertexs[j] << ":" << _matrix[i][j] << endl;
					}
				}
			}
		}

		void BFS(const V& src)
		{
			int srci = GetVertexIndex(src);
			queue<int> q; //广度遍历的队列
			vector<bool> visited(_vertexs.size(), false); //标记数组
			q.push(srci); //起点入队
			visited[srci] = true; //已经被遍历过了
			while (!q.empty())
			{
				int front = q.front();
				q.pop();
				cout << front << ":" << _vertexs[front] << endl;
				//把front顶点的邻接顶点入队列
				for (size_t i = 0; i < _matrix[front].size(); i++)
				{
					if (_matrix[front][i] != Max_W)
					{
						if (visited[i] == false)
						{
							q.push(i);
							visited[i] = true;
						}
					}
				}
			}
		} 

		void BFSLevel(const V& src)
		{
			int srci = GetVertexIndex(src);
			queue<int> q; //广度遍历的队列
			vector<bool> visited(_vertexs.size(), false); //标记数组
			q.push(srci); //起点入队
			visited[srci] = true; //已经被遍历过了
			int levelSize = 1;
			while (!q.empty())
			{
				for (int i = 0; i < levelSize; i++)
				{
					int front = q.front();
					q.pop();
					cout << front << ":" << _vertexs[front] << " ";
					//把front顶点的邻接顶点入队列
					for (size_t i = 0; i < _matrix[front].size(); i++)
					{
						if (_matrix[front][i] != Max_W)
						{
							if (visited[i] == false)
							{
								q.push(i);
								visited[i] = true;
							}
						}
					}
				}
				cout << endl;
				levelSize = q.size();
			}
		}
		void _DFS(size_t srci, vector<bool>& visited)
		{
			cout << srci << ":" << _vertexs[srci] << endl;
			visited[srci] = true;
			for (int i = 0; i < _matrix[srci].size(); i++)
			{
				if (_matrix[srci][i] != Max_W && visited[i] == false)
				{
					_DFS(i, visited);
				}
			}
		}
		void DFS(const V& src)
		{
			int srci = GetVertexIndex(src);
			vector<bool> visited(_vertexs.size(), false);
			_DFS(srci, visited);
		}

		struct Edge
		{
			int _srci;
			int _dsti;
			W _w;
			Edge(int srci, int dsti, W w)
				:_srci(srci)
				,_dsti(dsti)
				,_w(w)
			{}
			bool operator>(const Edge& e) const
			{
				return this->_w > e._w;
			}
		};

		//传入的是一个只有结点的，没有边的图
		W Kruskal(Self& minTree)
		{
			//先将所有的边，按照小堆的方式进行组织起来
			priority_queue<Edge, vector<Edge>, greater<Edge>> minque;
		   	size_t n = _vertexs.size();
			for (int i = 0; i < n; i++)
			{
				for (int j = 0; j < n; j++)
				{
					//由于这里是无向图，他是一个对称矩阵，但是我们的边只考虑一半就已经可以了。剩下的就重复了。
					if (i < j && _matrix[i][j] != Max_W)
					{
						//已经按照自身的，带有边的图，将所有的边的信息全部组织好了
						minque.push(Edge(i, j, _matrix[i][j]));
					}
				}
			}
			//因为最小生成树一定是n-1条边，所以我们现在要选出n-1条边，size是计数器
			int size = 0;
			//用于计算权值
			W totalW = W();
			//最关键的问题是判环，这里我们可以用并查集去检测是否这两个顶点在一个集合里面，如果在集合里面，说明一定是连通的，在加上就成环了
			UnionFindSet ufs(n);
			//开始选边，我们要考虑到所有的边
			while (!minque.empty())
			{
				//取出一个最小的边，然后就可以将他踢出优先级队列了，如果被选中不需要它了，如果没有被选中，那只能是因为出现环了才不要它了。
				Edge min = minque.top();
				minque.pop();
				//看看是否在一个集合里面，如果在一个集合里面，那么他们已经是连通了，没必要在连通，还想要连通那么一定是环！
				if (!ufs.InSet(min._srci, min._dsti))
				{
					//我们可以看看我们选出来的边
					cout << _vertexs[min._srci] << "-" << _vertexs[min._dsti] << ":" << min._w << endl;
					//该边是符合的，我们直接为这个图加上边
					minTree._AddEdge(min._srci, min._dsti, min._w);
					//加上之后，就连通了，我们让他们形成集合
					ufs.Union(min._srci, min._dsti);
					//我们一定只有n-1条边，我们需要计数
					++size;
					//将总的权值要加起来
					totalW += min._w;
				}
				//成环的情况，我们只是看看这是哪条边
				else
				{
					cout << "构成环啦！:";
					cout << _vertexs[min._srci] << "-" << _vertexs[min._dsti] << ":" << min._w << endl;
				}
			}
			//上面的循环中，如果图是连通的，那么最终一定选出来的是n-1条边。除非图是不连通的。
			if (size == n - 1)
			{
				return totalW;
			}
			//图不连通，直接返回0
			else
			{
				return W();
			}
		}


		W Prim(Self& minTree, const V& src)
		{
			size_t srci = GetVertexIndex(src);
			int n = _vertexs.size();
			//使用集合的方式
			//set<int> X;
			//set<int> Y;
			//X.insert(srci);
			//for (int i = 0; i < n; i++)
			//{
			//	if (i != srci)
			//	{
			//		Y.insert(i);
			//	}
			//}

			//利用vector的方式,去记录两个集合。
			vector<bool> X(n, false);
			vector<bool> Y(n, true);
			X[srci] = true;
			Y[srci] = false;

			//从X->Y集合中连接的边去选最小的边
			priority_queue<Edge, vector<Edge>, greater<Edge>> minq;
			//把目前为止X集合（仅仅只有起点）的相关的边，全部放入优先级队列中
			for (int i = 0; i < n; i++)
			{
				if (_matrix[srci][i] != Max_W)
				{
					minq.push(Edge(srci, i, _matrix[srci][i]));
				}
			}
			//size用来判断是否达到最小生成树的个数n-1,totalW用来计算权值之和
			size_t size = 0;
			W totalW = W();
			//我们开始在优先级队列中去寻找
			while (!minq.empty())
			{
				//在优先级队列中找到一个最小的元素，由于优先级队列中的一定是我们X集合可以延申的边。所以是满足Prim的选边条件的
				Edge min = minq.top();
				//如果边使用了，那么就不用了，如果不使用，那肯定是因为环才导致的，那也不要了
				minq.pop();
				//这里比较巧妙，因为根据我们的算法思想，我们选边的时候一定是从X集合的某一个顶点开始的，然后去找一个不在X集合里面的顶点
				//所以这里我们可以直接判断目的点是否在X集合里面，如果在，那么一定是环。如果不是，才可以把这条边给加上去
				if (X[min._dsti])
				{
					//cout << "构成环：";
					//cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl;
					continue;
				}

				//把边给加上去
				minTree._AddEdge(min._srci, min._dsti, min._w);
				//cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl;
				
				//X.insert(min._dsti);
				//Y.erase(min._dsti);
				
				//处理一下目的点的边
				X[min._dsti] = true;
				Y[min._dsti] = false;

				++size;
				totalW += min._w;
				//这里相当于一次优化，因为该循环一定可以保证选出来的n-1条边是最小生成树，
				//后面的优先级队列中的任何一条边一定会导致出现环，会在前面的检测目的点是否在X集合中被处理掉。
				//这里则是直接不用继续入其他的边进入队列了。可以提高一些效率，减少无用的操作
				if (size == n - 1)
				{
					break;
				}
				//当一条边添加完成后，它就属于X集合了，我们可以将该点所延申出的边给加入到优先级队列中
				//只有该边存在，且目的地没有被加入过的时候，才会入队列。值得耐人寻味的是，这里虽然已经处理过一次可能出现环的情况了
				//但是可能由于在添加边的时候，导致某些优先级队列中的边会导致构成环了，所以就有了前面的再次根据目的地时候在X集合中去判环
				for (int i = 0; i < n; i++)
				{
					if (_matrix[min._dsti][i] != Max_W && X[i] == false)
					{
						minq.push(Edge(min._dsti, i, _matrix[min._dsti][i]));
					}
				}
			}
			if (size == n - 1)
			{
				return totalW;
			}
			else
			{
				return W();
			}
		}

		void PrintShortPath(const V& src, const vector<W>& dist, const vector<int>& pPath)
		{
			size_t srci = GetVertexIndex(src);
			int n = _vertexs.size();
			for (int i = 0; i < n; i++)
			{
				if (i != srci)
				{
					cout << "[" << "pathlenth:" << dist[i] << "]";
					stack<int> path;
					size_t parent = i;
					while (parent != srci)
					{
						path.push(parent);
						parent = pPath[parent];
					}
					path.push(parent);
					cout << "path:";
					while (!path.empty())
					{ 
						int top = path.top();
						path.pop();
						cout << _vertexs[top] << "->";
					}
					cout << "nullptr" << endl;

				}
			}

		}
		//src是起始结点，dist数组的内容是存放最短路径值的权值，即每个元素的内容代表着从起始结点到该结点的最短路径
		//pPath数组是路径的数组，因为有时候我们需要求出路径的具体走法，所以我们可以用数组的方式，类似于并查集去寻找路径的方式，建立一颗树
		void Dijkstra(const V& src, vector<W>& dist, vector<int>& pPath)
		{
			//确定好起始结点的下标
			size_t srci = GetVertexIndex(src);
			int n = _vertexs.size();
			//我们先让所有的最短路径无穷。即还未求出来
			dist.resize(n, Max_W);
			//注意源节点到源节点的最短路径一定是0
			dist[srci] = 0;
			//我们让所有的路径都设置为-1，意味着所有的结点都没有找出来最短路径
			pPath.resize(n, -1);
			//这是表示起点它的路径就是它自己，这步其实只是为了让起点和为求出最短路径给分开表示。不然都用-1可能会混乱
			pPath[srci] = srci;
			//这个S集合代表我们已经求出最短路径的集合。如果是true代表着这个结点早已求出了最短路径。false代表未求出
			vector<bool> S(n, false);
			//注意这里我们做一下特殊处理，虽然我们起点它本来就应该放在这个集合里面，但是我们还是先让它为false。这里我们其实是想与下面的循环进行合并
			//所以迫不得已做的操作，因为一旦将某个结点设置为true，那么它的相邻的结点路径也应该被更新一下，那么这里就要把下面的对于代码拷贝一份。
			//所以为了让代码简洁，我们直接不写这一步了，和下面的进行合并
			//S[srci] = true;

			//这里只是控制一下循环次数，因为我们要求所有的结点都要被遍历一下，而每次只会遍历一个结点，即将一个结点给放入S集合。
			//我们每次点亮的一定是之前从未遍历过的结点
			for(int j = 0; j < n; j++)
			{
				//Dijkstra算法要求每次都要找出一个，还没有被访问过的（不在S集合的），并且是有路径的，且路径是当前最小的一个结点
				//对于第一次找到的就是srci以及所对应的0值
				int u = 0;
				W min = Max_W;
				for (int i = 0; i < n; i++)
				{
					if (S[i] == false && dist[i] < min)
					{
						u = i;
						min = dist[i];
					}
				}
				//找到以后，我们可以让他加入S集合，代表它已经被访问过了。借助这里找到了srci，并且使他加入到S集合
				S[u] = true;
				//松弛更新u连接顶点v， srci->u + u->v < srci->v 就更新
				//注意，这里我们需要的是找到我们新加入S集合的邻接的顶点，然后判断是不是需要更新最短路径，
				//但是我们一开始并不知道，所以我们遍历所有的结点，依次判断条件是否满足
				for (int v = 0; v < n; v++)
				{
						//我们这个要更新的不能是我们之前已经访问过的了。因为之前访问过的一定是最短路径了！
					if (S[v] == false &&
						//因为是要邻接的顶点，它必须要直接连通的两个顶点。所以用这个条件进行排除
						_matrix[u][v] != Max_W
						//这是为了看一看用这个算出来的是不是小于我们原来的路径，如果是，那么最短路径就变成它了
						&& dist[u] + _matrix[u][v] < dist[v])
					{
						//更新最短路径
						dist[v] = dist[u] + _matrix[u][v];
						//更新路径的树
						pPath[v] = u;
					}
				}
			}
		}

		bool BellmanFord(const V& src, vector<W>& dist, vector<int>& parentPath)
		{
			size_t n = _vertexs.size();
			size_t srci = GetVertexIndex(src);

			dist.resize(n, Max_W);
			dist[srci] = W();
			parentPath.resize(n, -1);
			parentPath[srci] = srci;
			
			for (int k = 0; k < n; k++)
			{
				bool update = false;
				for (int i = 0; i < n; i++)
				{
					for (int j = 0; j < n; j++)
					{
						update = true;
						//srci->i + i->j => srci->j
						if (_matrix[i][j] != Max_W && dist[i] + _matrix[i][j] < dist[j])
						{
							dist[j] = dist[i] + _matrix[i][j];
							parentPath[j] = i;
						}
					}
				}
				if (update == false)
				{
					break;
				}
			}
			//还能更新就是带有负权回路
			for (int i = 0; i < n; i++)
			{
				for (int j = 0; j < n; j++)
				{
					//srci->i + i->j => srci->j
					if (_matrix[i][j] != Max_W && dist[i] + _matrix[i][j] < dist[j])
					{
						return false;
					}
				}
			}

		}

		//vvDist中，vvDist[i][j]代表着以i为起点，到j的最短路径
		//vvpPath中，vvpPath[i][j]代表着以i为起点，j为终点的最短路径的上一个父路径。
		void FloydWarShall(vector<vector<W>>& vvDist, vector<vector<int>>& vvpPath)
		{
			size_t n = _vertexs.size();
			vvDist.resize(n, vector<W>(n, Max_W));
			vvpPath.resize(n, vector<int>(n, -1));
			//把直接相连的边更新一下
			for (int i = 0; i < n; i++)
			{
				for (int j = 0; j < n; j++)
				{
					if (_matrix[i][j] != Max_W)
					{
						vvDist[i][j] = _matrix[i][j];
						//i和j直接相连，即i->j，那么j的上一个父路径一定是i
						vvpPath[i][j] = i;
					}
					if (i == j)
					{
						vvDist[i][j] = W();
					}
				}
			}
			//最短路径的更新，k要考虑每一个结点作为中间结点
			for (int k = 0; k < n; k++)
			{
				for (int i = 0; i < n; i++)
				{
					for (int j = 0; j < n; j++)
					{
						//k作为中间结点去尝试更新所有的i->j路径
						if (vvDist[i][k] != Max_W && vvDist[k][j] != Max_W
							&& vvDist[i][k] + vvDist[k][j] < vvDist[i][j])
						{
							vvDist[i][j] = vvDist[i][k] + vvDist[k][j];
							// 从i到j的父路径
							// 也就是说如果K和j直接相连，那么它的父路径就是k本身，而此时vvPath[k][j]正好就是k本身
							// 如果k和j不直接相连，即 i->...->k->...->x->j,此时父路径就是x,而此时vvpPath[k][j]的值其实也是x
							vvpPath[i][j] = vvpPath[k][j];
						}
					}
				}

				//打印一下权值和路径矩阵
				for (int i = 0; i < n; i++)
				{
					for (int j = 0; j < n; j++)
					{
						if (vvDist[i][j] == Max_W)
						{
							printf("%3c", '*');
						}
						else
						{
							printf("%3d", vvDist[i][j]);
						}
					}
					cout << endl;
				}
				cout << endl;
				for (int i = 0; i < n; i++)
				{
					for (int j = 0; j < n; j++)
					{
						printf("%3d", vvpPath[i][j]);
					}
					cout << endl;
				}
				cout << "=================" << endl;



			}


		} 


	private:
		vector<V> _vertexs; //顶点集合
		map<V, int> _indexMap; //顶点对应的下标关系
		vector<vector<W>> _matrix; //临界矩阵
	};


	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.PrintShortPath(str[i], vvDist[i], vvParentPath[i]);
			cout << endl;
		}
	}

	void TestGraphBellmanFord()
	{
		//const char* str = "syztx";
		//Graph<char, int, INT_MAX, true> g(str, strlen(str));
		//g.AddEdge('s', 't', 6);
		//g.AddEdge('s', 'y', 7);
		//g.AddEdge('y', 'z', 9);
		//g.AddEdge('y', 'x', -3);
		//g.AddEdge('z', 's', 2);
		//g.AddEdge('z', 'x', 7);
		//g.AddEdge('t', 'x', 5);
		//g.AddEdge('t', 'y', 8);
		//g.AddEdge('t', 'z', -4);
		//g.AddEdge('x', 't', -2);
		//vector<int> dist;
		//vector<int> parentPath;
		//if (g.BellmanFord('s', dist, parentPath))
		//{
		//	g.PrintShortPath('s', dist, parentPath);
		//}
		//else
		//{
		//	cout << "存在负权回路" << endl;
		//}
		//微调图结构，带有负权回路的测试
		const char* str = "syztx";
		Graph<char, int, INT_MAX, true> g(str, strlen(str));
		g.AddEdge('s', 't', 6);
		g.AddEdge('s', 'y', 7);
		g.AddEdge('y', 'x', -3);
		g.AddEdge('y', 'z', 9);
		g.AddEdge('y', 'x', -3);
		g.AddEdge('y', 's', 1); // 新增
		g.AddEdge('z', 's', 2);
		g.AddEdge('z', 'x', 7);
		g.AddEdge('t', 'x', 5);
		g.AddEdge('t', 'y', -8); // 更改
		g.AddEdge('t', 'z', -4);
		g.AddEdge('x', 't', -2);
		vector<int> dist;
		vector<int> parentPath;
		if (g.BellmanFord('s', dist, parentPath))
		{
		 g.PrintShortPath('s', dist, parentPath);
		}
		else
		{
		 cout << "存在负权回路" << endl;
		}
	}


	void TestGraphDijkstra()
	{
		//const char* str = "syztx";
		//Graph<char, int, INT_MAX, true> g(str, strlen(str));
		//g.AddEdge('s', 't', 10);
		//g.AddEdge('s', 'y', 5);
		//g.AddEdge('y', 't', 3);
		//g.AddEdge('y', 'x', 9);
		//g.AddEdge('y', 'z', 2);
		//g.AddEdge('z', 's', 7);
		//g.AddEdge('z', 'x', 6);
		//g.AddEdge('t', 'y', 2);
		//g.AddEdge('t', 'x', 1);
		//g.AddEdge('x', 'z', 4);
		//vector<int> dist;
		//vector<int> parentPath;
		//g.Dijkstra('s', dist, parentPath);
		//g.PrintShortPath('s', dist, parentPath);

		const char* str = "sytx";
		Graph<char, int, INT_MAX, true> g(str, strlen(str));
		g.AddEdge('s', 't', 10);
		g.AddEdge('s', 'y', 5);
		g.AddEdge('t', 'y', -7);
		g.AddEdge('y', 'x', 3);
		vector<int> dist;
		vector<int> parentPath;
		g.Dijkstra('s', dist, parentPath);
		g.PrintShortPath('s', dist, parentPath);

	}



	void TestGraph()
	{
		Graph<char, int, INT_MAX, true> g("0123", 4);
		g.AddEdge('0', '1', 1);
		g.AddEdge('0', '3', 4);
		g.AddEdge('1', '3', 2);
		g.AddEdge('1', '2', 9);
		g.AddEdge('2', '3', 8);
		g.AddEdge('2', '1', 5);
		g.AddEdge('2', '0', 3);
		g.AddEdge('3', '2', 6);
		g.Print();
	}
	void TestGraphBDFS()
	{
		string a[] = { "张三", "李四", "王五", "赵六", "周七" };
		Graph<string, int> g1(a, sizeof(a) / sizeof(string));
		g1.AddEdge("张三", "李四", 100);
		g1.AddEdge("张三", "王五", 200);
		g1.AddEdge("王五", "赵六", 30);
		g1.AddEdge("王五", "周七", 30);
		g1.Print();
		g1.BFS("张三");
		cout << endl;
		g1.BFSLevel("张三");
		cout << endl;
		g1.DFS("张三");
	}
	void TestGraphMinTree()
	{
		const char* str = "abcdefghi";
		Graph<char, int> g(str, strlen(str));
		g.AddEdge('a', 'b', 4);
		g.AddEdge('a', 'h', 8);
		//g.AddEdge('a', 'h', 9);
		g.AddEdge('b', 'c', 8);
		g.AddEdge('b', 'h', 11); 
		g.AddEdge('c', 'i', 2);
		g.AddEdge('c', 'f', 4);
		g.AddEdge('c', 'd', 7);
		g.AddEdge('d', 'f', 14);
		g.AddEdge('d', 'e', 9);
		g.AddEdge('e', 'f', 10);
		g.AddEdge('f', 'g', 2);
		g.AddEdge('g', 'h', 1);
		g.AddEdge('g', 'i', 6);
		g.AddEdge('h', 'i', 7);
		//Graph<char, int> kminTree;
		//Graph<char, int> kminTree(str, strlen(str));
		//cout << "Kruskal:" << g.Kruskal(kminTree) << endl;
		//kminTree.Print();
		//Graph<char, int> pminTree(str, strlen(str));
		//cout << "Prim:" << g.Prim(pminTree, 'a') << endl;
		//pminTree.Print();

		for (int i = 0; i < strlen(str); i++)
		{
			Graph<char, int> pminTree(str, strlen(str));
			cout << "Prim:" << str[i] << ":" << g.Prim(pminTree, str[i]) << endl;
		}
	}
}

运行结果为

image-20240224161523162

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/420961.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

项目解决方案：社会视频资源接入平台解决方案

项目解决方案：社会视频资源接入平台解决方案

目 录 一、项目背景 二、方案简述 1、监控功能 2、视频录像 三、系统构架 四、产品功能及特点 1、实时图像点播 2. 远程控制 3. 存储和备份 4. 历史图像的检索和回放 5、报警管理 &#xff08;1&#xff09;报警配置 &#xff08;2&#xff09;报警的…
阅读更多...
优化Vue项目中 WebStorm:2023.3 对 CSS 和 HTML 的默认注释

优化Vue项目中 WebStorm:2023.3 对 CSS 和 HTML 的默认注释

前言 WebStorm是一种基于JetBrains IntelliJ平台的集成开发环境&#xff08;IDE&#xff09;&#xff0c;专门用于Web开发。它支持JavaScript、HTML和CSS等语言&#xff0c;并提供了丰富的功能和工具&#xff0c;以提高开发人员的效率。但是&#xff0c;在开发Vue项目中发现&a…
阅读更多...
通过实验验证GAP、GMP、FC性能表现

通过实验验证GAP、GMP、FC性能表现

深度学习 文章目录 深度学习一、背景二、什么是GAP三、GAP在Keras中的定义四、GAP VS GMP VS FC五、结论 一、背景 Global Average Pooling(简称GAP&#xff0c;全局池化层)技术最早提出是可以替代全连接层的一种新技术。在keras发布的经典模型中&#xff0c;可以看到不少模型…
阅读更多...
Cy8c42（2.软件串口使用）

Cy8c42（2.软件串口使用）

1.前言 原本早上想开始用可编程逻辑模块来做RS寄存器的&#xff0c;但是RS寄存器要两个输入&#xff0c;板载只有一个按键&#xff0c;那就先看看串口吧&#xff0c;把串口作为一个按键用。 2.初始化 芯片内部一共有两种串口 &#xff08;1&#xff09;软件串口&#xff08…
阅读更多...
企业数字化转型的第一步：由被动多云向主动多云转变

企业数字化转型的第一步：由被动多云向主动多云转变

随着经济环境、市场形势、技术发展、用户需求等诸多因素的变化&#xff0c;数字化转型为企业进一步提升效率和竞争力、提供更加丰富的个性化产品和服务、进行业务场景创新、探寻新的增长机会和运营模式提供了崭新的途径。越来越多的企业意识到&#xff0c;数字化转型已不是企业…
阅读更多...
【嵌入式——QT】数值输入和显示组件

【嵌入式——QT】数值输入和显示组件

数值输入和显示组件 QSlider&#xff1a;滑动条&#xff0c;通过滑动来设置数值&#xff1b;QScrollBar&#xff1a;卷滚条&#xff0c;与QSlider类似&#xff0c;还可以用于卷滚区域&#xff1b;QProgressBar&#xff1a;进度条&#xff0c;一般用于显示任务进度&#xff0c;…
阅读更多...
【Leetcode每日一题】二分查找 - 在排序数组中查找元素的第一个和最后一个位置（难度⭐⭐）（18）

【Leetcode每日一题】二分查找 - 在排序数组中查找元素的第一个和最后一个位置（难度⭐⭐）（18）

1. 题目解析 Leetcode链接&#xff1a;34. 在排序数组中查找元素的第一个和最后一个位置 这个问题的理解其实相当简单&#xff0c;只需看一下示例&#xff0c;基本就能明白其含义了。 核心在于找到给定目标值所在的数组下标区间&#xff0c;设计一个O(logn)的算法。 2. 算法原…
阅读更多...
集成测试之我的初步学习与总结

集成测试之我的初步学习与总结

基本概念 将软件集成起来后进行测试。 集成测试又叫子系统测试、组装测试、部件测试等。集成测试主要是针对软件高层设计进行测试&#xff0c;一般来说是以模块和子系统为单位进行测试。 集成测试包含的层次 模块内的集成&#xff0c;主要是测试模块内各个接口间的交互集成…
阅读更多...
【C++】用文件流的put和get成员函数读写文件

【C++】用文件流的put和get成员函数读写文件

题目 编写一个mycopy程序&#xff0c;实现文件复制的功能。用法是在控制台输入&#xff1a; mycooy 源文件名 目标文件名 参数介绍 m a i n main main 函数的参数有两个&#xff0c;一个int类型参数和一个指针数组。 a r g c argc argc 表示参数的个数。参数为void时 a r g …
阅读更多...
Github上最值得学习的10个Android开源项目，安卓面试题

Github上最值得学习的10个Android开源项目，安卓面试题

1.Java语言进阶与Android相关技术核 Android应用是由Java语言进行开发的&#xff0c;SDK也是由Java语言编写&#xff0c;对于Android来说&#xff0c;只要SDK没有用Kotlin重写&#xff0c;那么Java语言是都需要学习的。而且Android APK的后台服务器程序大概率是Java语言构建&a…
阅读更多...
一【初识EMC】

一【初识EMC】

在作为硬件行业相关从业者&#xff0c;经常接触到EMC相关问题&#xff0c;下面来简单介绍下EMC相关方面的知识 文章目录 前言一、生活中的EMC现象&#xff1f;二、EMC是什么三、EMC的三要素四、EMI与EMS的评估方式1.RE2.CE3.HAR4.FLICKER5.Rs6.CS7.ESD8.EFT9.DIP10.PMS11.surge…
阅读更多...
内置kpi接口短视频解析html源码

内置kpi接口短视频解析html源码

内置kpi接口短视频解析html源码&#xff0c;复制代码即可解析视频并 去水印 源码免费下载地址专业知识分享社区-专业知识笔记免费分享 (chaobiji.cn)
阅读更多...
flutter旋转动画，Android彻底组件化方案实践方法

flutter旋转动画，Android彻底组件化方案实践方法

Android基础 & 常用 针对Android基础&常用知识&#xff0c;我认为对于初级开发者来说&#xff0c;按照优先级最主要的知识点主要包括&#xff1a;四大组件、布局使用、多线程 & 动画&#xff1b;具体介绍如下&#xff1a; 2. Android进阶 针对Android进阶知识&am…
阅读更多...
Java通过Semaphore控制同一时间只有3个线程运行

Java通过Semaphore控制同一时间只有3个线程运行

怎么控制同一时间只有3个线程运行&#xff1f; 直接上代码 import java.util.Date; import java.util.concurrent.ExecutorService; import java.util.concurrent.Executors; import java.util.concurrent.Semaphore;public class SemaphoreThreadPoolExample {private static…
阅读更多...
精酿啤酒：从原料到成品的质量控制流程

精酿啤酒：从原料到成品的质量控制流程

质量控制是啤酒酿造过程中重要的一环&#xff0c;它涉及到从原料选择到成品生产的每一个环节。Fendi Club啤酒对其质量控制流程有着严格的要求&#xff0c;以确保产品的品质和一致性。 Fendi Club啤酒对原料的选择进行严格把关。他们选用上好、新鲜的麦芽、水和酵母等原料&…
阅读更多...
MySql安全加固：可信IP地址访问控制 设置密码复杂度

MySql安全加固：可信IP地址访问控制 设置密码复杂度

MySql安全加固&#xff1a;可信IP地址访问控制 & 设置密码复杂度 1.1 可信IP地址访问控制1.2 设置密码复杂度 &#x1f496;The Begin&#x1f496;点点关注&#xff0c;收藏不迷路&#x1f496; 1.1 可信IP地址访问控制 当您在创建用户时使用’%作为主机部分&#xff0c;…
阅读更多...
zookeeper启动报错

zookeeper启动报错

启动zookeeper报错 从报错中可以看到 Invalid config, exiting abnormally 意思是&#xff1a;配置无效&#xff0c;异常退出 在往上看是没有zoo.cof这个配置文件 2024-02-27 14:47:03,285 [myid:] - ERROR [main:o.a.z.s.q.QuorumPeerMain99] - Invalid config, exiting…
阅读更多...
怎样进入powershell状态？怎样获取powershell的help信息？

怎样进入powershell状态？怎样获取powershell的help信息？

进入powershell的方法之一&#xff1a;在dos命令窗口运行powershell命令&#xff0c;系统输出版权信息&#xff0c;命令行提示符前面出现PS 标志。说明系统进入powerrshell状态&#xff08;如下图&#xff09;。 获取powershell的help信息方法&#xff1a; 在powershell命令行…
阅读更多...
android适配器adapter，Android程序员架构之路该如何继续学习

android适配器adapter，Android程序员架构之路该如何继续学习

便于开发的插件、工具和第三方开源库 1.GsonFormat 使用方法&#xff1a;快捷键AltS也可以使用AltInsert选择GsonFormat&#xff0c;作用&#xff1a;速将json字符串转换成一个Java Bean&#xff0c;免去我们根据json字符串手写对应Java Bean的过程。 2.ButterKnife Zelezny …
阅读更多...
Windows批处理：bat文件学习

Windows批处理：bat文件学习

目录 第一章、快速了解Windows批处理1.1&#xff09;Windows批处理相关概念介绍1.1.1&#xff09;批处理的起源1.1.2&#xff09;bat文件介绍 1.2&#xff09;Demo1.2.1&#xff09;创建文件添加命令1.2.2&#xff09;bat脚本中的命令解释 第二章、实例2.1&#xff09;点击bat文…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站