// src是選定的起點(diǎn)，dist記錄起點(diǎn)到各點(diǎn)的最短路徑，pPath記錄到每個(gè)點(diǎn)的最短路徑的前驅(qū)頂點(diǎn)下標(biāo)
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;
		// 已經(jīng)確定最短路徑的頂點(diǎn)集合
		vector<bool> S(n, false);
		for (size_t j = 0; j < n; ++j)
		{
			// 選最短路徑頂點(diǎn)且不在S更新其他路徑
			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連接頂點(diǎn)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;
				}
			}
		}
}

bool BellmanFord(const V& src, vector<W>& dist, vector<int>& pPath)
{
		size_t n = _vertexs.size();
		size_t srci = GetVertexIndex(src);
		// vector<W> dist,記錄srci-其他頂點(diǎn)最短路徑權(quán)值數(shù)組
		dist.resize(n, MAX_W);
		// vector<int> pPath 記錄srci-其他頂點(diǎn)最短路徑父頂點(diǎn)數(shù)組
		pPath.resize(n, -1);
		// 先更新srci->srci為缺省值
		dist[srci] = W();
		// 總體最多更新n輪
		for (size_t k = 0; k < n; ++k)
		{
			// i->j 更新松弛
			bool update = false;
			cout << "更新第:" << k << "輪" << endl;
			for (size_t i = 0; i < n; ++i)
			{
				for (size_t j = 0; j < n; ++j)
				{
					// srci -> i + i ->j
					if (_matrix[i][j] != MAX_W && dist[i] != MAX_W && dist[i] + _matrix[i][j] < dist[j])
	 			    {
						update = true;
						//cout << _vertexs[i] << "->" << _vertexs[j] << ":" << _matrix[i][j] << endl;
						dist[j] = dist[i] + _matrix[i][j];
						pPath[j] = i;
					}
				}
			}
			// 如果這個(gè)輪次中沒(méi)有更新出更短路徑，那么后續(xù)輪次就不需要再走了
			if (update == false)
			{
				break;
			}
		}
		// 還能更新就是帶負(fù)權(quán)回路
		for (size_t i = 0; i < n; ++i)
		{
			for (size_t j = 0; j < n; ++j)
			{
				// srci -> i + i ->j
				if (_matrix[i][j] != MAX_W && dist[i] + _matrix[i][j] < dist[j])
				{
					return false;
				}
			}
		}
		return true;
}

void FloydWarshall(vector<vector<W>>& vvDist, vector<vector<int>>& vvpPath)
{
		size_t n = _vertexs.size();
		vvDist.resize(n);
		vvpPath.resize(n);
		// 初始化權(quán)值和路徑矩陣
		for (size_t i = 0; i < n; ++i)
		{
			vvDist[i].resize(n, MAX_W);
			vvpPath[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];
					vvpPath[i][j] = i;
				}
				if (i == j)
				{
					vvDist[i][j] = W();
				}
			}
		}
		// 最短路徑的更新i-> {其他頂點(diǎn)} ->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)
				{
					// k 作為的中間點(diǎn)嘗試去更新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];
							// 找跟j相連的上一個(gè)鄰接頂點(diǎn)
							// 如果k->j 直接相連，上一個(gè)點(diǎn)就k，vvpPath[k][j]存就是k
							// 如果k->j 沒(méi)有直接相連，k->...->x->j，vvpPath[k][j]存就是x
						vvpPath[i][j] = vvpPath[k][j];
					}
				}
			}
		}	
}