图的最短路径算法

//最小起始边
void Dijkstra(const V& src, vector<W>& dist, vector<int>& pPath)  //有负权值会失效
{
	size_t srci = GetVertexIndex(src);
	size_t n = _vertexs.size();
	dist.resize(n, MAX_W);
	pPath.resize(n, -1);

	dist[srci] = 0;
	pPath[srci] = srci;

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

	for(size_t j = 0;j<n ;j++)
	{
		//选最短路径的顶点更新其他路径

		int u = 0;
		W min = MAX_W;
		for (size_t i = 0; i < n; i++)
		{
			if (S[i] == false && dist[i] < min)
			{
				u = i;
				min = dist[i];
			}

		}
		S[u] = true;//更新u连接v srci->u  u->v  srci->v
		for (size_t 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;
			}
		}
	}
}









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;//找出i顶点的路径
			size_t parent = i;
			while (parent != srci)
			{
				path.push_back(parent);
				parent = pPath[parent];
			}
			path.push_back(srci);
			reverse(path.begin(), path.end());

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










bool Bellman_ford(const V&src , vector<W>&dist , vector<int> & pPath)  //找终止边  解决不了负权回路
{
	size_t n = _vertexs.size();
	size_t srci = GetVertexIndex(src);

	dist.resize(n, MAX_W);//记录srci 其他顶点最短路径权值数组

	pPath.resize(n, -1); // 记录srci 其他顶点最短路径父顶点数组

	dist[srci] = W();//先更新srci->srci为缺省值

	for (size_t k = 0; k < n; k++)  //i->j暴力更新k次  总体最多更新n轮
	{
		bool updata = false;
		for (size_t i = 0; i < n; i++)
		{
			for (size_t j = 0; j < n; j++)
			{
				if (_matrix[i][j] != MAX_W && dist[i] + _matrix[i][j] < dist[j])
				{
					updata = true;
					dist[j] = dist[i] + _matrix[i][j];
					pPath[j] = i;
				}
			}
		}
		if (updata == false) //没更新就退出 不需要走了
		{
			break;
		}
	}

	for (size_t i = 0; i < n; i++) //还能更新就是带负权回路
	{
		for (size_t j = 0; j < n; j++)
		{
			if (_matrix[i][j] != MAX_W && dist[i] + _matrix[i][j] < dist[j])
			{
				return false;
			}
		}
	}
	return true;
}









void floyd( 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); // n行
	}

	//直接相连的边更新一下
	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个顶点最多
	//把所有点都作为中间点 k作为中间点 是任意点 去更新i->j
	for (size_t k = 0; k < n; k++)
	{
		for (size_t i = 0; i < n; i++)
		{
			for (size_t j = 0; j < n; 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];

					//找跟j相连的结点
					//如果k直接和j相连 vvpath[k][j] = k
					//如果k不和j相连 k->..x->j  vvpath[k][j]=x
					vvpPath[i][j] = vvpPath[k][j];
				}
			}
		}
	}

	// 打印权值和路径矩阵观察数据
	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;
}