【数据结构】最短路径算法实现（Dijkstra（迪克斯特拉），FloydWarshall（弗洛伊德） ）

---

前言

最短路径问题：从在带权有向图G中的某一顶点出发，找出一条通往另一顶点的最短路径，最短也就是沿路径各边的权值总和达到最小。
单源最短路径问题：给定一个图G = ( V ， E ) G=(V，E)G=(V，E)，求源结点s ∈ V s∈Vs∈V到图
中每个结点v ∈ V v∈Vv∈V的最短路径

一、Dijkstra（迪克斯特拉）

1.方法：

针对一个带权有向图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中，所以该算法使用的是贪心策略。

核心就是从当前选入的顶点当中去找其直接相连的最小的边，然后用这个最小边相连的另一个顶点为起点，找与其直接相连边中最小的边（eg：与s直接相连的为t，y。最小的边为5，即y顶点，其为s到y的最短距离，然后以y为起点，与y直接相连的有t，x，z。最小的边为2即z点，y到z最短为2，所以s到z最短为7，以此类推，直到所有点都被当过起点后结束）

2.代码实现

void Dijkstra(const V& src, vector<W>& dist, vector<int>& pPath)
		{
			//dist存的src到其他点的最短路径
			// vector<int> pPath 记录srci-其他顶点最短路径父顶点数组
			size_t srci = GetVertexIndex(src);
			size_t n = _vertexs.size();
			dist.resize(n, MAX_W);
			pPath.resize(n, -1);

			dist[srci] = 0;//自己到自己距离为0
			pPath[srci] = srci;

			// 已经确定最短路径的顶点集合
			vector<bool> S(n, false);

			for (size_t j = 0; j < n; ++j)
			{
				 
				int u = srci;//u为当前最短路径顶点
				W min = MAX_W;//min为起始点到u的距离
				for (size_t i = 0; i < n; ++i)
				{
					if (S[i] == false && dist[i] < min)
					{
						u = i;
						min = dist[i];
					}
				}


				//找到与当前起始点直接相连的最短路径的顶点后
				//将其位置置为true表明已经选入
				S[u] = true;
				// 松弛算法：更新一遍u连接的所有边，看是否能更新出更短连接路径
				for (size_t v = 0; v < n; ++v)
				{
					// 如果srci->u + u->k 比 srci->k更短 则进行更新
					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;
					}
				}
			}
		}


//打印路径
void PrintShortPath(const V& src, const vector<W>& dist, const vector<int>& pPath) {
	
			size_t srci = GetVertexIndex(src);
			size_t n = _vertexs.size();
			for (size_t i = 0; i < n; i++) {
				if (i != srci) {
					vector<int>path;
					//path为src到其他顶点路径
					size_t parenti = i;
					while (parenti != srci) {
						path.push_back(parenti);
						parenti = pPath[parenti];
					}
					path.push_back(srci);
					//需要反转一下，因为我们从s->x->v
					//是从v的父亲为x再推出x的父亲为s才结束的
					reverse(path.begin(), path.end());

					for (auto index : path) {
						cout << _vertexs[index] << "->";
					}
					cout << "权值和：" << dist[i] << endl;
				}
			}
		 }

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

二、FloydWarshall（弗洛伊德）

多源最短路径：Floyd-Warshall算法是解决任意两点间的最短路径的一种算法。

1.方法

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}取得的一条最短路径。

核心将中间经过的k当成所经过s->…->j中间经过的所有中间顶点集合中的一个，把中间的所有顶点看成k。

2.代码实现

void FloydWarshall(vector<vector<W>>& vvDist, vector<vector<int>>& vvpPath)
		{
			size_t n = _vertexs.size();
			vvDist.resize(n);
			vvpPath.resize(n);

			// 初始化权值和路径矩阵
			for (size_t i = 0; i < n; ++i)
			{
				vvDist[i].resize(n, MAX_W);
				vvpPath[i].resize(n, -1);
			}
			//vvpPath[i][j]表示i->j,j的父亲为i




			// 直接相连的边更新一下
			//把目前已知直接相连的边放入vvDist中，并更新vvpPath[i][j]
			for (size_t i = 0; i < n; ++i)
			{
				for (size_t j = 0; j < n; ++j)
				{
					if (_matrix[i][j] != MAX_W)
					{
						vvDist[i][j] = _matrix[i][j];
						vvpPath[i][j] = i;
					}

					if (i == j)
					{
						vvDist[i][j] = W();
					}
				}
			}

			 
			// 最短路径的更新i-> {其他顶点} ->j
			//这里要进行k次的原因是因为我们所有结点都有可能
			//成为src与dst的中间结点，所以要考虑所有情况
			for (size_t k = 0; k < n; ++k)
			{
				for (size_t i = 0; i < n; ++i)
				{
					for (size_t 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];

							 

							vvpPath[i][j] = vvpPath[k][j];
							//因为这里k实际上是中间顶点集合
							// 找跟j相连的上一个邻接顶点
							// 如果k->j 直接相连，上一个点就k，vvpPath[k][j]存就是k
							// 如果k->j 没有直接相连，k->...->x->j，vvpPath[k][j]存就是x
						}
					}
				}

				// 打印权值和路径矩阵观察数据
				for (size_t i = 0; i < n; ++i)
				{
					for (size_t j = 0; j < n; ++j)
					{
						if (vvDist[i][j] == MAX_W)
						{
							//cout << "*" << " ";
							printf("%3c", '*');
						}
						else
						{
							//cout << vvDist[i][j] << " ";
							printf("%3d", vvDist[i][j]);
						}
					}
					cout << endl;
				}
				cout << endl;

				for (size_t i = 0; i < n; ++i)
				{
					for (size_t j = 0; j < n; ++j)
					{
						//cout << vvParentPath[i][j] << " ";
						printf("%3d", vvpPath[i][j]);
					}
					cout << endl;
				}
				cout << "=================================" << endl;
			}
		}
	 
	};

完整源码

如果对Graph这些代码不太熟悉的小伙伴可以参考我之前写的【数据结构】图的创建（邻接矩阵，邻接表）以及深度广度遍历（BFS,DFS）

namespace matrix {
	//V为顶点类型，W为边权值类型，MAX_W为权值最大值也就是无效值
	//Direction用来判断是不是有向图，false为无向图
	template<class V,class W,W  MAX_W=INT_MAX,bool Direction=false>
	class Graph {
	public:
		Graph() = default;
		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;
				//将顶点存入_vertexs，下标映射存进map
			}

			_matrix.resize(n);
			for (size_t i = 0; i < _matrix.size(); i++) {
				_matrix[i].resize(n, MAX_W);
				//邻接矩阵默认初始值为无效值
			}
		}

		size_t GetVertexIndex(const V& v) {
			//获得对应顶点在数组中的下标
			auto it = _indexMap.find(v);
			if (it != _indexMap.end()) {
				return it->second;
				//有这个顶点返回其下标
			}
			else {
				throw("顶点不存在");
				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) {
			//添加边与顶点的关系。从src到dst方向的关系
			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;


			//打印邻接矩阵
			for (size_t i = 0; i < _matrix.size(); i++) {
				cout << i << " ";
				for (size_t j = 0; j < _matrix[i].size(); j++) {
					if (_matrix[i][j] == MAX_W) {
						printf("%4c", '*');
					}
					else {
						printf("%4d", _matrix[i][j]);
					}
				}
				cout << endl;
			 }
		}

	 
	 


		void BFS(const V& src) {
			size_t srci = GetVertexIndex(src);
			queue<int>q;
			q.push(srci);
			vector<bool>visited(_vertexs.size(), false);
			visited[srci] = true;//标记这个顶点被访问过了
			int levelSize = 1;
			while (!q.empty()) {
				//levelSize为当前层的大小
				for (size_t i = 0; i < levelSize; i++) {
					int front = q.front();
					q.pop();
					cout << front << ":" << _vertexs[front]<<" ";

					for (size_t i = 0; i < _vertexs.size(); i++) {
						if (_matrix[front][i] != MAX_W && visited[i] == false) {
							q.push(i);
							visited[i] = true;//标记这个顶点被访问过了
						}
					}
				}
				levelSize = q.size();//更新当前层的数量
				cout << endl;
			}
			cout << endl;
		}


		void _DFS(size_t srci, vector<bool>& visited) {
			cout << srci << ":" << _vertexs[srci] << endl;
			visited[srci] = true;//标记这个顶点被访问过了
			for (size_t i = 0; i < _vertexs.size(); i++) {
				if (_matrix[srci][i] != MAX_W && visited[i] == false) {
					_DFS(i, visited);
				}
			}
		}

		void DFS(const V& src) {
			size_t srci = GetVertexIndex(src);
			vector<bool>visited(_vertexs.size(), false);

			_DFS(srci, visited);
		}


 

	 
		 
		
		
		 

		typedef Graph<V, W, MAX_W, false> Self;

		//建立边的类，保存边的两个顶点下标和权值
		struct Edge {
			size_t _srci;
			size_t _dsti;
			W _w;

			Edge(size_t srci,size_t dsti,W w)
				:_srci(srci),
				_dsti(dsti),
				_w(w)
			{}

			bool operator>(const Edge& e)const {
				return _w > e._w;//小根堆判断
			}

		};

		W Kruskal(Self& minTree)
		{
			//minTree为最小生成树，刚开始什么都没有
			size_t n = _vertexs.size();

			//初始化最小生成树
			minTree._vertexs = _vertexs;
			minTree._indexMap = _indexMap;
			minTree._matrix.resize(n);
			for (size_t i = 0; i < n; ++i)
			{
				minTree._matrix[i].resize(n, MAX_W);
			}


			//我们每次选边从全部边中选出最小的（保证不构成回路的情况）
			//所以我们可以考虑用小根堆来存入边，这样每次方便找最小的
			priority_queue<Edge, vector<Edge>, greater<Edge>> minque;
			for (size_t i = 0; i < n; ++i)
			{
				for (size_t j = 0; j < n; ++j)
				{
					if (i < j && _matrix[i][j] != MAX_W)
					{
						//将所有有效值边放进堆中
						minque.push(Edge(i, j, _matrix[i][j]));
					}
				}
			}

			 
			int size = 0;
			W totalW = W();
			UnionFindSet ufs(n); 

			// 选出n-1条边
			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);
					++size;
					totalW += min._w;//权值总和增加
				}
				else
				{
					//cout << "构成环：";
					//cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl;
				}
				 
			}

			if (size == n - 1)//边数选够说明最小生成树
				//创建成功
			{
				return totalW;
			}
			else
			{
				return W();
			}
		}

		W Prim(Self& minTree, const W& src)
		{
			size_t srci = GetVertexIndex(src);
			size_t n = _vertexs.size();

			minTree._vertexs = _vertexs;
			minTree._indexMap = _indexMap;
			minTree._matrix.resize(n);
			for (size_t i = 0; i < n; ++i)
			{
				minTree._matrix[i].resize(n, MAX_W);
			}

			 

			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;

			// 先把srci连接的边添加到小根堆中
			for (size_t i = 0; i < n; ++i)
			{
				if (_matrix[srci][i] != MAX_W)
				{
					minq.push(Edge(srci, i, _matrix[srci][i]));
				}
			}

			cout << "Prim开始选边" << endl;
			size_t size = 0;//选出边的数量
			W totalW = W();//权值之和
			while (!minq.empty())
			{
				Edge min = minq.top();
				minq.pop();

				// 最小边的目标点也在X集合，则构成环
				if (X[min._dsti])
				{
					//cout << "构成环:";
					//cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl;
				}
				else
				{
					//从Y中选出顶点
					minTree._AddEdge(min._srci, min._dsti, min._w);//加入最小生成树
					//cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl;
					X[min._dsti] = true;
					Y[min._dsti] = false;
					++size;
					totalW += min._w;
					if (size == n - 1)
						break;

					//把新加入顶点相关的边都放入小根堆中
					for (size_t i = 0; i < n; ++i)
					{
						if (_matrix[min._dsti][i] != MAX_W && Y[i])
						{
							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);
			size_t n = _vertexs.size();
			for (size_t i = 0; i < n; i++) {
				if (i != srci) {
					vector<int>path;
					//path为src到其他顶点路径
					size_t parenti = i;
					while (parenti != srci) {
						path.push_back(parenti);
						parenti = pPath[parenti];
					}
					path.push_back(srci);
					//需要反转一下，因为我们从s->x->v
					//是从v的父亲为x再推出x的父亲为s才结束的
					reverse(path.begin(), path.end());

					for (auto index : path) {
						cout << _vertexs[index] << "->";
					}
					cout << "权值和：" << dist[i] << endl;
				}
			}
		 }



		void Dijkstra(const V& src, vector<W>& dist, vector<int>& pPath)
		{
			//dist存的src到其他点的最短路径
			// vector<int> pPath 记录srci-其他顶点最短路径父顶点数组
			size_t srci = GetVertexIndex(src);
			size_t n = _vertexs.size();
			dist.resize(n, MAX_W);
			pPath.resize(n, -1);

			dist[srci] = 0;//自己到自己距离为0
			pPath[srci] = srci;

			// 已经确定最短路径的顶点集合
			vector<bool> S(n, false);

			for (size_t j = 0; j < n; ++j)
			{
				 
				int u = srci;//u为当前最短路径顶点
				W min = MAX_W;//min为起始点到u的距离
				for (size_t i = 0; i < n; ++i)
				{
					if (S[i] == false && dist[i] < min)
					{
						u = i;
						min = dist[i];
					}
				}


				//找到与当前起始点直接相连的最短路径的顶点后
				//将其位置置为true表明已经选入
				S[u] = true;
				// 松弛算法：更新一遍u连接的所有边，看是否能更新出更短连接路径
				for (size_t v = 0; v < n; ++v)
				{
					// 如果srci->u + u->k 比 srci->k更短 则进行更新
					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;
					}
				}
			}
		}
		void FloydWarshall(vector<vector<W>>& vvDist, vector<vector<int>>& vvpPath)
		{
			size_t n = _vertexs.size();
			vvDist.resize(n);
			vvpPath.resize(n);

			// 初始化权值和路径矩阵
			for (size_t i = 0; i < n; ++i)
			{
				vvDist[i].resize(n, MAX_W);
				vvpPath[i].resize(n, -1);
			}
			//vvpPath[i][j]表示i->j,j的父亲为i




			// 直接相连的边更新一下
			//把目前已知直接相连的边放入vvDist中，并更新vvpPath[i][j]
			for (size_t i = 0; i < n; ++i)
			{
				for (size_t j = 0; j < n; ++j)
				{
					if (_matrix[i][j] != MAX_W)
					{
						vvDist[i][j] = _matrix[i][j];
						vvpPath[i][j] = i;
					}

					if (i == j)
					{
						vvDist[i][j] = W();
					}
				}
			}

			 
			// 最短路径的更新i-> {其他顶点} ->j
			//这里要进行k次的原因是因为我们所有结点都有可能
			//成为src与dst的中间结点，所以要考虑所有情况
			for (size_t k = 0; k < n; ++k)
			{
				for (size_t i = 0; i < n; ++i)
				{
					for (size_t 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];

							 

							vvpPath[i][j] = vvpPath[k][j];
							//因为这里k实际上是中间顶点集合
							// 找跟j相连的上一个邻接顶点
							// 如果k->j 直接相连，上一个点就k，vvpPath[k][j]存就是k
							// 如果k->j 没有直接相连，k->...->x->j，vvpPath[k][j]存就是x
						}
					}
				}

				// 打印权值和路径矩阵观察数据
				for (size_t i = 0; i < n; ++i)
				{
					for (size_t j = 0; j < n; ++j)
					{
						if (vvDist[i][j] == MAX_W)
						{
							//cout << "*" << " ";
							printf("%3c", '*');
						}
						else
						{
							//cout << vvDist[i][j] << " ";
							printf("%3d", vvDist[i][j]);
						}
					}
					cout << endl;
				}
				cout << endl;

				for (size_t i = 0; i < n; ++i)
				{
					for (size_t j = 0; j < n; ++j)
					{
						//cout << vvParentPath[i][j] << " ";
						printf("%3d", vvpPath[i][j]);
					}
					cout << endl;
				}
				cout << "=================================" << endl;
			}
		}
	private:
		vector<V>_vertexs;//顶点集合
		map<V, int>_indexMap;//存顶点与数组下标的映射关系
		vector<vector<W>>_matrix;//邻接矩阵
	};



 }