算法：最短路径

本篇总结的是图当中的最短路径算法

Dijkstra算法

单源最短路径问题：给定一个图G = ( V ， E ) G=(V，E)G=(V，E)，求源结点s ∈ V s∈Vs∈V到图中每个结点v ∈ V v∈Vv∈V的最短路径。Dijkstra算法就适用于解决带权重的有向图上的单源最短路径问题，同时算法要求图中所有边的权重非负。一般在求解最短路径的时候都是已知一个起点和一个终点，所以使用Dijkstra算法求解过后也就得到了所需起点到终点的最短路径。针对一个带权有向图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算法存在的问题是不支持图中带负权路径，如果带有负权路径，则可能会找不到一些路径的最短路径

那么下面用一个例子来说明这个算法：

Dijkstra算法是解决最短路劲中的常用算法，它的局限性在于不能求带有负权的图

下面是代码实现的过程

		// Dijkstra求最短路径
		void Dijkstra(V vertex, vector<W>& warray, vector<size_t>& parentpath)
		{
			size_t srci = GetVertexsIndex(vertex);
			// 创建两个数组，一个数组用来存最短权值，一个数组存路径，并进行数据的初始化
			warray.resize(_vertexs.size(), W_MAX);
			parentpath.resize(_vertexs.size(), W_MAX);
			warray[srci] = W();
			parentpath[srci] = srci;
			// 用一个vector用来记录每个顶点是否都被选过了
			vector<bool> check(_vertexs.size(), false);

			// 每个顶点都用贪心算法找一次
			for (size_t num = 0; num < _vertexs.size(); num++)
			{
				// 定义一些变量，用来寻找到某个顶点最短的路径值和这个顶点的值
				W minW = W_MAX;
				size_t u = 0;
				// 首先遍历一次全部顶点，寻找从起点到该点路径最短的点
				for (size_t i = 0; i < _vertexs.size(); i++)
				{
					// 如果这个顶点没有被选过，并且这个顶点和起点之间联通，就把它选进来
					if (check[i] == false && warray[i] != W_MAX && warray[i] < minW)
					{
						minW = warray[i];
						u = i;
					}
				}
				// 运行到这里，就找出了到起点位置距离最短的顶点和具体的值，分别为minw和u
				check[u] = true;
				// 此时进行松弛算法，更新这个点到周围延伸出的顶点的路径值
				for (size_t j = 0; j < _vertexs.size(); j++)
				{
					// _vertexs[j]这个顶点经过_vertexs[u]到起点的距离小于它现在的值，那么就进行更新
					if (check[j] == false && _matrix[u][j] != W_MAX && warray[u] + _matrix[u][j] < warray[j])
					{
						// 此时说明可以进行更新
						warray[j] = warray[u] + _matrix[u][j];
						parentpath[j] = u;
					}
				}
			}
		}

为了便于观察，实现一个打印路径的逻辑算法，思路还是很简单的

		// 打印最短路径的逻辑算法
		void PrinrtShotPath(const V& src, const vector<W>& dist, const vector<size_t>& parentPath)
		{
			size_t srci = GetVertexsIndex(src);
			for (size_t i = 0; i < _vertexs.size(); ++i)
			{
				if (i == srci)
					continue;
				vector<size_t> path;
				size_t parenti = i;
				while (parenti != srci)
				{
					path.push_back(parenti);
					parenti = parentPath[parenti];
				}
				path.push_back(srci);
				reverse(path.begin(), path.end());
				for (auto pos : path)
				{
					cout << _vertexs[pos] << "->";
				}
				cout << dist[i] << endl;
			}
		}

Dijkstra算法的时间复杂度是O(N^2)

Bellman-Ford算法

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

简单来说，Bellman算法就是一个暴力枚举的过程，虽然时间复杂度高，但是确实是可以枚举出带有负权的图的结果

		// Bellman求最短路径
		bool Bellman(V vertex, vector<W>& warray, vector<size_t>& parentpath)
		{
			size_t srci = GetVertexsIndex(vertex);
			// 创建两个数组，一个数组用来存最短权值，一个数组存路径，并进行数据的初始化
			warray.resize(_vertexs.size(), W_MAX);
			parentpath.resize(_vertexs.size(), W_MAX);
			warray[srci] = W();
			parentpath[srci] = srci;

			// 有k条边，每次更新一次边就刷新一次
			for (int k = 0; k < _vertexs.size(); k++)
			{
				for (int i = 0; i < _vertexs.size(); i++)
				{
					for (int j = 0; j < _vertexs.size(); j++)
					{
						// 运行到这里进入到邻接矩阵中，分别看一下路径长短并进行更新
						// 如果从起点到j的距离大于从起点到i，再从i到j的整体距离，此时就进行更新
						if (_matrix[i][j] != W_MAX && warray[i] + _matrix[i][j] < warray[j])
						{
							warray[j] = warray[i] + _matrix[i][j];
							parentpath[j] = i;
						}
					}
				}
			}

			// 判断一下是不是带有负权的环，如果带有环，就返回false
			for (int i = 0; i < _vertexs.size(); i++)
			{
				for (int j = 0; j < _vertexs.size(); j++)
				{
					// 如果还是能更新，就说明带负权的环了
					if (_matrix[i][j] != W_MAX && warray[i] + _matrix[i][j] < warray[j])
					{
						return false;
					}
				}
			}

			return false;
		}

Floyd-Warshall

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

void FloydWarShall(vector<vector<W>>& vvDist, vector<vector<int>>& vvParentPath)
		{
			size_t N = _vertexs.size();
			vvDist.resize(N);
			vvParentPath.resize(N);
			// 初始化权值和路径矩阵
			for (size_t i = 0; i < N; ++i)
			{
				vvDist[i].resize(N, MAX_W);
				vvParentPath[i].resize(N, -1);
			}
			// 将直接相连的路径初始化
			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];
						vvParentPath[i][j] = i;
					}
					else
					{
						vvParentPath[i][j] = -1;
					}
					if (i == j)
					{
						vvDist[i][j] = 0;
						vvParentPath[i][j] = -1;
					}
				}
			}
			// 依次用顶点k作为中转点更新最短路径
			for (size_t k = 0; k < N; ++k)
			{
				for (size_t i = 0; i < N; ++i)
				{
					for (size_t j = 0; j < N; ++j)
					{
						// i->k + k->j 比 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];
							vvParentPath[i][j] = vvParentPath[k][j];
						}
					}
				}
			}
		}