图的最短路径

最短路径

概念

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

分类

1. 单源最短路径: 从某个源点到其它各顶点的最短路径.

• Dijkstra算法
• Bellman-Ford算法

2. 多源最短路径: 每一对顶点之间的最短路径.

• Floyd-Warshall算法
• 每次以一个顶点为源点重复调用单源最短路径算法n次

Dijkstra算法

给定一个带权图G的每条边(v_i,v_j)上的权值都是非负实数. 另外, 给定V中的一个顶点s充当源点.

基本思想: 按路径长度递增的次序来产生最短路径算法.

把V分成两组:

1. S: 已求出最短路径的顶点集合.
2. Q=V-S: 尚未确定最短路径的顶点集合, 将V-S中顶点按最短路径递增的次序加入到S中.

S是已经确定最短路径的顶点集合, 在初始时为空(初始时就可以将源节点s放入，毕竟源节点到自己的代价是0).

Q 为其余未确定最短路径的顶点集合, 每次从Q中找出一个源顶点s到该顶点代价最小的顶点u, 将u从Q中移出并放入S中, 对u的每一个相邻结点v进行松弛操作.

松弛即对每一个相邻结点v, 判断源顶点s到顶点u的代价与u到v的代价之和是否比原来s到v的代价更小, 若代价比原来小则要将s到v的代价更新为s到u与u到v的代价之和, 否则维持原样.

如此一直循环直至集合Q为空, 即所有顶点都已经查找过一遍并确定了最短路径, 至于一些源点s到达不了的顶点在算法循环后其代价仍为初始设定的值, 不会发生变化.

Dijkstra算法每次都是选择V-S中最小的路径顶点来进行更新, 并加入S中所以该算法使用的是贪心策略。

dist[] : 记录从源点s到其它顶点当前的最短路径长度. 初始时源点s对应的元素为0, 其它为无穷大.

pPath[] : pPath[i]表示从源点到顶点i之间的最短路径的前驱顶点的下标. 初始时全为-1, 在算法结束时, 可根据其下标值追溯得到源点s到顶点i的最短路径.

邻接表

邻接矩阵

通过dist[]与pPath[]打印源点s到其它顶点的最短路径:

void PrintShortPath(const V& src, const vector<W>& dist, const vector<int>& pPath)
{
    int srci = GetVertexIndex(src);
    if (srci == -1)
    {
        return;
    }

    int n = (int)_vertexSet.size();

    for (int i = 0; i < n; i++)
    {
        if (i != srci)
        {
            int p = i;
            vector<int> v;
            // 先获取源点s到某顶点的路径
            while (pPath[p]!=-1)
            {
                v.push_back(p);
                p = pPath[p];
            }
            v.push_back(p);
            // 打印路径和对应的代价
            for (int j = (int)(v.size() - 1); j >= 0; j--)
            {
                std::cout << _vertexSet[v[j]] << "-->";
            }
            std::cout << dist[i] << std::endl;
        }
    }
}

邻接表与邻接矩阵的测试:

需要注意的是, 对于含有负权值边的图Dijkstra算法不支持:

Dijkstra算法是贪心算法, 当最小取进来后, 不会返回去重新计算. 如从A出发, 先选C代价为6, 之后A到达C的路径不会再去更新, 因为C已经加入到了S集合.

要解决含有负权值边的图需要用到Bellman-Ford算法.

时间性能分析:

对于一个含有n个顶点和e条边的有向图, 基于邻接表与邻接矩阵的Dijkstra算法的时间复杂度为O(n₂).

Bellman-Ford算法

Dijkstra算法只能用来解决正权值图的单源最短路径问题, 但有些题目会出现负权图. 这时这个算法就不能帮助我们解决问题了, 而bellman—ford算法可以解决负权值图的单源最短路径问题.

它的优点是可以解决有负权值边的单源最短路径问题, 而且可以用来判断是否有负权回路. 但时间效率低.

负权值回路问题什么算法都无法解决, 因为会陷入死循环.

Bellman-Ford算法的主要思想是: 对于起始顶点s和某终止顶点j, 是否能通过顶点i, 使s->i->j的代价小于s->j. 如果成立则进行代价dist和路径pPath更新.

邻接表

邻接矩阵

邻接表与邻接矩阵的测试:

Floyd-Warshall算法

Floyd算法是典型的动态规划, 自底向上分别求解子问题的解, 然后由这些子问题的解得到原问题的解. 这个算法的时间复杂度是O(n₃), 但形式上比较简单.

Floyd算法步骤:

1. 初始化vvDist矩阵, 若v_i到v_j没有边弧, 则vvDist[i] [j]=∞; 若i==j, 则vvDist[i] [j]=0; 否则, 若v_i到v_j存在边弧, 则vvDist[i] [j]=weight(v_i, v_j).
2. 对于每一个顶点v_k, 若vvDist[i] [k]+vvDist[k] [j] < vvDist[i] [j]成立, 表明从v_i经过v_k再到v_j的路径比原来v_i到v_j的路径短, 则更新vvDist[i] [j]=vvDist[i] [k]+vvDist[k] [j].
3. 将图中n个顶点依次加入每对顶点间进行探测, 最终矩阵vvDist中记录的便是每对顶点间的最短路径的长度.

邻接表

邻接矩阵

邻接表与邻接矩阵的测试:

源代码

邻接表

#define _CRT_SECURE_NO_WARNINGS 1

#include <unordered_set>
#include <functional>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <map>

using namespace std;

namespace AdjacentList
{
	template<typename W>
	struct Edge
	{
		int _dsti;
		W _weight;

		struct Edge<W>* _next;

		Edge(int dsti, const W& weight)
			:_dsti(dsti)
			, _weight(weight)
			, _next(nullptr)
		{}
	};

	template<typename V, typename W, bool Directed = false>
	class Graph
	{
		using Edge = Edge<W>;
	private:
		std::vector<V> _vertexSet; // 顶点的集合
		std::map<V, int> _vertexIndex; // 顶点映射下标
		std::vector<Edge*> _table; // 出度边表
	public:

		typedef Graph<V, W, Directed> Self;

		Graph() = default;

		Graph(const V* a, int n)
		{
			for (int i = 0; i < n; i++)
			{
				AddVertex(a[i]);
			}
		}

		int GetVertexIndex(const V& v)
		{
			typename std::map<V, int>::iterator pos = _vertexIndex.find(v);
			if (pos != _vertexIndex.end())
			{
				return pos->second;
			}
			else
			{
				return -1;
			}
		}

		bool AddVertex(const V& v)
		{
			if (GetVertexIndex(v) != -1)
				return false;

			_vertexSet.push_back(v);

			_vertexIndex.insert(std::make_pair(v, _vertexSet.size() - 1));

			_table.push_back(nullptr);

			return true;
		}

		bool _AddEdge(int srci, int dsti, const W& weight)
		{
			Edge* edge = new Edge(dsti, weight);

			// 头插
			edge->_next = _table[srci];
			_table[srci] = edge;

			// 无向图
			if (!Directed)
			{
				edge = new Edge(srci, weight);

				edge->_next = _table[dsti];
				_table[dsti] = edge;
			}

			return true;
		}

		bool AddEdge(const V& src, const V& dst, const W& weight)
		{
			int srci = GetVertexIndex(src);
			int dsti = GetVertexIndex(dst);

			// 顶点不在图中,添加边失败
			if (srci == -1 || dsti == -1)
				return false;

			return _AddEdge(srci, dsti, weight);
		}

		void PrintShortPath(const V& src, const vector<W>& dist, const vector<int>& pPath)
		{
			int srci = GetVertexIndex(src);
			if (srci == -1)
			{
				return;
			}

			int n = (int)_vertexSet.size();

			for (int i = 0; i < n; i++)
			{
				if (i != srci)
				{
					int p = i;
					vector<int> v;

					while (pPath[p] != -1)
					{
						v.push_back(p);
						p = pPath[p];
					}
					v.push_back(p);

					for (int j = (int)(v.size() - 1); j >= 0; j--)
					{
						std::cout << _vertexSet[v[j]] << "-->";
					}
					std::cout << dist[i] << std::endl;
				}
			}
		}

		const W& _GetEdgeWeight(int srci, int dsti)
		{
			Edge* curr = _table[srci];
			while (curr != nullptr)
			{
				if (curr->_dsti == dsti)
				{
					return curr->_weight;
				}
				curr = curr->_next;
			}
			return W();
		}

		template<W W_MAX> // 非类型模板参数,邻接表需要提供W_MAX表示无法到达
		void Dijkstra(const V& src, vector<W>& dist, vector<int>& pPath)
		{
			int srci = GetVertexIndex(src);
			if (srci == -1)
			{
				return;
			}

			int n = static_cast<int>(_vertexSet.size());

			dist.resize(n, W_MAX);
			pPath.resize(n, -1);

			// true表示在S集合中,false表示不在S集合中
			std::vector<bool> S(n, false); // 开始时都不在S以便统一处理

			// 开始时,src到自己的代价为W()
			dist[srci] = W();

			for (int k = 0; k < n; k++)
			{
				int u = -1;
				W min = W_MAX;
				// 寻找不在S集合中且当前从src到自己距离最小的顶点
				for (int i = 0; i < n; i++)
				{
					if (!S[i] && dist[i] < min)
					{
						u = i;
						min = dist[i];
					}
				}

				// 没有找到就无需松弛更新
				if (u == -1)
				{
					continue;
				}

				// 再将u对应的顶点加入S集合中
				S[u] = true;

				// 找到了就进行松弛更新
				Edge* vNode = _table[u];

				while (vNode != nullptr)
				{
					// 只有dsti对应的顶点不在S集合才能继续判断
					if (!S[vNode->_dsti]&&
						dist[u] + vNode->_weight < dist[vNode->_dsti])
					{
						dist[vNode->_dsti] = dist[u] + vNode->_weight;
						pPath[vNode->_dsti] = u; // 更新路径
					}
					vNode = vNode->_next;
				}
			}
		}

		template<W W_MAX>
		bool BellmanFord(const V& src, vector<W>& dist, vector<int>& pPath)
		{
			int srci = GetVertexIndex(src);
			if (srci == -1)
			{
				return false;
			}

			int n = static_cast<int>(_vertexSet.size());
			// 初始化dist与pPath
			dist.resize(n, W_MAX);
			pPath.resize(n, -1);

			dist[srci] = W();

			for (int k = 0; k < n; k++) // 进行n轮更新即可
			{
				bool flag = true; // 标识是否有新的短路径产生
				for (int i = 0; i < n; i++)
				{
					Edge* jNode = _table[i];
					// 进行松弛更新判断
					while (jNode != nullptr)
					{
						// 如果s->...->i->j < s->...->j成立则更新
						if (dist[i] + jNode->_weight < dist[jNode->_dsti])
						{
							dist[jNode->_dsti] = dist[i] + jNode->_weight;
							pPath[jNode->_dsti] = i;
							flag = false;
						}
						jNode = jNode->_next;
					}
				}
				// 如果没有新的短路径产生,则其他的路径也无需进行迭代
				if (flag)
				{
					break;
				}
			}
			// 如果进行了n轮松弛更新还能产生新的短路径则说明有负权值回路
			for (int i = 0; i < n; i++)
			{
				Edge* jNode = _table[i];

				while (jNode != nullptr)
				{
					if (dist[i] + jNode->_weight < dist[jNode->_dsti])
					{
						return false;
					}
					jNode = jNode->_next;
				}
			}

			return true;
		}

		template<W W_MAX>
		void FloydWarshall(vector<vector<W>>& vvDist, vector<vector<int>>& vvpPath)
		{
			int n = static_cast<int>(_vertexSet.size());
			// 初始化vvDist与vvpPath
			vvDist.resize(n, vector<W>(n, W_MAX));
			vvpPath.resize(n, vector<int>(n, -1));

			for (int i = 0; i < n; i++)
			{
				// 对角线置为零
				vvDist[i][i] = 0;
				Edge* curr = _table[i];

				while (curr != nullptr)
				{
					vvDist[i][curr->_dsti] = curr->_weight;
					vvpPath[i][curr->_dsti] = i;
					curr = curr->_next;
				}
			}

			// 打印权值和路径矩阵观察数据
			for (size_t i = 0; i < n; ++i)
			{
				for (size_t j = 0; j < n; ++j)
				{
					if (vvDist[i][j] == W_MAX)
					{
						//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;

			for (int k = 0; k < n; k++)
			{
				for (int i = 0; i < n; i++)
				{
					for (int j = 0; j < n; j++)
					{
						// k顶点所在的行与列及正对角线无需更新
						if (k == i || k == j || i == j)
						{
							continue;
						}
						if (vvDist[i][k] != W_MAX && vvDist[k][j] != W_MAX
							&& vvDist[i][k] + vvDist[k][j] < vvDist[i][j])
						{
							// 条件满足则进行更新
							vvDist[i][j] = vvDist[i][k] + vvDist[k][j];
							// 更新直接父路径顶点下标
							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] == W_MAX)
						{
							//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;
			}	
		}
	};

	void TestGraphDijkstra()
	{
			const char* str = "syztx";
			Graph<char, int, 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> pPath;
			g.Dijkstra<INT_MAX>('s', dist, pPath);
			g.PrintShortPath('s', dist, pPath);

			// 图中带有负权路径时，贪心策略则失效了。
			// 测试结果可以看到s->t->y之间的最短路径没更新出来
			/*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);*/

			//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;
			//g.Dijkstra('s', dist, parentPath);
			//g.PrintShortPath('s', dist, parentPath);
	}

	void TestGraphBellmanFord()
	{
			const char* str = "syztx";
			Graph<char, int, 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> pPath;
			g.BellmanFord<INT_MAX>('s', dist, pPath);
			g.PrintShortPath('s', dist, pPath);

		//const char* str = "syztx";
		//Graph<char, int, 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('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', 'y', 8);

		//g.AddEdge('t', 'z', -4);
		//g.AddEdge('x', 't', -2);
		//vector<int> dist;
		//vector<int> parentPath;
		//if (g.BellmanFord<INT_MAX>('s', dist, parentPath))
		//	g.PrintShortPath('s', dist, parentPath);
		//else
		//	cout << "带负权回路" << endl;
	}

	void TestFloydWarShall()
	{
		const char* str = "12345";
		Graph<char, int, 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<INT_MAX>(vvDist, vvParentPath);

		// 打印任意两点之间的最短路径
		for (size_t i = 0; i < strlen(str); ++i)
		{
			g.PrintShortPath(str[i], vvDist[i], vvParentPath[i]);
			cout << endl;
		}
	}
}

int main()
{
	//AdjacentList::TestGraphDijkstra();
	//AdjacentList::TestGraphBellmanFord();
	AdjacentList::TestFloydWarShall();
	return 0;
}

邻接矩阵

#define _CRT_SECURE_NO_WARNINGS 1
#include <unordered_set>
#include <functional>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <map>

using namespace std;

namespace AdjacentMatrix
{
	template<typename V, typename W, W W_MAX, bool Directed = false>
	class Graph
	{
	private:
		std::vector<V> _vertexSet;
		std::map<V, int> _vertexIndex;
		std::vector<std::vector<W>> _matrix;
	public:

		typedef Graph<V, W, W_MAX, Directed> Self;

		Graph() = default;

		Graph(const V* a, int n)
		{
			for (int i = 0; i < n; i++)
			{
				AddVertex(a[i]);
			}
		}

		int GetVertexIndex(const V& v)
		{
			typename std::map<V, int>::iterator pos = _vertexIndex.find(v);
			if (pos != _vertexIndex.end())
			{
				return pos->second;
			}
			else
			{
				return -1;
			}
		}

		bool AddVertex(const V& v)
		{
			// 顶点存在不需要继续增加
			if (GetVertexIndex(v) != -1)
				return false;

			_vertexSet.push_back(v);
			_vertexIndex.insert(std::make_pair(v, _vertexSet.size() - 1));

			// 先在原有的行上一列
			for (int i = 0; i < (int)_matrix.size(); i++)
			{
				_matrix[i].push_back(W_MAX);
			}

			// 增加一行
			_matrix.push_back(std::vector<W>(_vertexSet.size(), W_MAX));

			return true;
		}

		bool AddEdge(const V& src, const V& dst, const W& weight)
		{
			int srci = GetVertexIndex(src);
			int dsti = GetVertexIndex(dst);

			// 顶点不在图中,添加边失败
			if (srci == -1 || dsti == -1)
				return false;

			return _AddEdge(srci, dsti, weight);
		}

		bool _AddEdge(int srci, int dsti, const W& weight)
		{
			// 顶点不在图中,添加边失败
			if (srci == -1 || dsti == -1)
				return false;

			_matrix[srci][dsti] = weight;

			// 如果为无向图,则需要再添加一条dst->src的边
			if (!Directed)
			{
				_matrix[dsti][srci] = weight;
			}

			return true;
		}

		void PrintShortPath(const V& src, const vector<W>& dist, const vector<int>& pPath)
		{
			int srci = GetVertexIndex(src);
			if (srci == -1)
			{
				return;
			}

			int n = (int)_vertexSet.size();

			for (int i = 0; i < n; i++)
			{
				if (i != srci)
				{
					int p = i;
					vector<int> v;
					// 先获取源点s到某顶点的路径
					while (pPath[p]!=-1)
					{
						v.push_back(p);
						p = pPath[p];
					}
					v.push_back(p);
					// 打印路径和对应的代价
					for (int j = (int)(v.size() - 1); j >= 0; j--)
					{
						std::cout << _vertexSet[v[j]] << "-->";
					}
					std::cout << dist[i] << std::endl;
				}
			}
		}

		void Dijkstra(const V& src, vector<W>& dist, vector<int>& pPath)
		{
			int srci = GetVertexIndex(src);
			if (srci == -1)
			{
				return;
			}

			int n = (int)_vertexSet.size();

			// 先将dist与pPath初始化
			dist.resize(n, W_MAX); // 开始都是最大代价
			// 保存的是到该顶点的前一个顶点的下标(a->b->c对于c顶点保存b顶点下标)
			pPath.resize(n, -1); 

			dist[srci] = W();

			// 记录src到哪些顶点已经有最短路径了
			vector<bool> S(n, false);

			for (int k = 0; k < n; k++)
			{
				int u = -1;
				W min = W_MAX;

				for (int i = 0; i < n; i++)
				{
					if (!S[i] && min > dist[i])
					{
						u = i;
						min = dist[i];
					}
				}

				if (u == -1) // 没有在Q集合中找到最小距离的顶点则通过松弛更新
				{
					continue;
				}

				S[u] = true;

				// 松弛更新
				for (int v = 0; v < n; v++)
				{
					if (!S[v] && _matrix[u][v] != W_MAX
						&& 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)
		{
			int srci = GetVertexIndex(src);
			if (srci == -1)
			{
				return false;
			}

			int n = (int)_vertexSet.size();

			// 记录srci到其他顶点最短路径权值数组,开始都是最大代价
			dist.resize(n, W_MAX); 
			// 保存的是到该顶点的前一个顶点的下标(a->b->c对于c顶点保存b顶点下标)
			pPath.resize(n, -1); 

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

			// 总体最多更新n轮
			for (int k = 0; k < n; k++)
			{
				int flag = true;
				for (int i = 0; i < n; i++)
				{
					for (int j = 0; j < n; j++)
					{
						// 判断核心思想是否成立:如果s->...->i->j < s->...->j成立则更新
						if (_matrix[i][j] != W_MAX && dist[i] + _matrix[i][j] < dist[j])
						{
							dist[j] = dist[i] + _matrix[i][j];
							pPath[j] = i;
							flag = false;
						}
					}
				}

				if (flag) // 如果没再更新出最短路径,则后续轮次就不需要再走了
				{
					break;
				}
			}

			// 检查是否有负权值回路问题, 还能更新就是带负权回路
			for (int i = 0; i < n; i++)
			{
				for (int j = 0; j < n; j++)
				{
					if (_matrix[i][j] != W_MAX && dist[i] + _matrix[i][j] < dist[j])
					{
						return false;
					}
				}
			}
			return true;
		}

		void FloydWarshall(vector<vector<W>>& vvDist, vector<vector<int>>& vvpPath)
		{
			int n = static_cast<int>(_vertexSet.size());

			vvDist.resize(n, vector<W>(n, W_MAX));
			vvpPath.resize(n, vector<int>(n, -1));

			// 初始化vvDist
			for (int i = 0; i < n; i++)
			{
				for (int j = 0; j < n; j++)
				{
					if (i == j) // 对角线置为0,int()==0
					{
						vvDist[i][j] = W();
					}
					else if (_matrix[i][j] != W_MAX)
					{
						vvDist[i][j] = _matrix[i][j];
						vvpPath[i][j] = i;
					}
				}
			}

			for (int k = 0; k < n; k++)
			{
				for (int i = 0; i < n; i++)
				{
					for (int j = 0; j < n; j++)
					{
						if (k == i || k == j || i == j)
						{
							continue;
						}
						// 更新迭代
						if (vvDist[i][k]!=W_MAX && vvDist[k][j]!=W_MAX&&
							vvDist[i][k] + vvDist[k][j] < vvDist[i][j])
						{
							vvDist[i][j] = vvDist[i][k] + vvDist[k][j];
							vvpPath[i][j] = vvpPath[k][j];
						}
					}
				}
			}

		}
	};

	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> pPath;
			g.Dijkstra('s', dist, pPath);
			g.PrintShortPath('s', dist, pPath);

			 图中带有负权路径时，贪心策略则失效了。
			 测试结果可以看到s->t->y之间的最短路径没更新出来
			//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);

			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;
			g.Dijkstra('s', dist, parentPath);
			g.PrintShortPath('s', dist, parentPath);
	}

	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> pPath;
			g.BellmanFord('s', dist, pPath);
			g.PrintShortPath('s', dist, pPath);

		//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('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', '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 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;
		}
	}
}

int main()
{
	//AdjacentMatrix::TestGraphDijkstra();
	//AdjacentMatrix::TestGraphBellmanFord();

	AdjacentMatrix::TestFloydWarShall();

	return 0;
}