图的最短路径（C++实现图【4】）

目录

1. 最短路径

1.1单源最短路径--Dijkstra算法

代码实现

1.2 单源最短路径--Bellman-Ford算法

代码实现

1.3 多源最短路径--Floyd-Warshall算法

代码实现

---

1. 最短路径

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

1.1单源最短路径--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算法存在的问题是不支持图中带负权路径，如果带有负权路径，则可能会找不到一些路径的最短路径。

我来通俗地讲解一下它的逻辑，假设我们选择s点作为我们的起点，那么我们从s点出发的直接路径有两条，一条是到y的5，一条是到t的10，我们选择最短的就是到y点（但是我们的s到t的10距离实际上也是被我们记录下来的），并将y点加入到我们的S集合中，因为不可能有值比我们从s到y还要短的路径了（这一步很好理解，我们试想一下，我们从一点能出来很多条路径到不同目的地，此时我们选其中一条最短的，那么这个时候哪怕其它路径经过一路转折也不可能再比我们选的这条要短，因为其它路光是到他的下一个点就已经大于我们所选的这条路径了，更不用说后面还要再经过不知道多少个点），将y的点加入到我们的S集合之后，我们就要从s，y两点出发继续我们的操作（我们要注意我们是从S集合里面去找它们的路径），还是一样，从y点我们能出来3条直接路径，我们选择最短的将z加入到S中（并把其它两条路也记录一下【这就叫松弛更新（后面我就不重复了都是一样的）】），我们再从s，y，z中继续寻找，我们找到了y到g的路径，将g加入S，最后就是我们的x了。

代码实现

//迪杰斯特拉最短单源路径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++){//选最短路径顶点且不在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连接顶点v srci->u  u->vfor (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;}}}}

        我们先来思考一下，虽然我们知道了迪杰斯特拉算法的大致逻辑，但是我们的细节是怎样的呢？比如我们如何记录路径，又怎么来进行松弛更新？这里，我给出一种方法，我们来两个变量就能搞定了（这里就是我们的两个空的形参dist，pPath），dist就用来存放我们的起点到这个点（下标映射）的权值用来辅助我们松弛更新，pPath就是用来存这个点的父亲是谁（有点类似并查集的思路），这样我们的路径就可以记录了。这也就是我们这两个形参的意思，第一个新参就是起点。

        在了解完三个形参的作用之后，我们先来进行初始化的操作，我们先要获取起点的下标，还有顶点的个数，我们要对dist和pPath进行初始化，dist对象的初始值我们就设置为整型最大值，pPath对象的初始值我们就设置成-1.然后给我们的起点的权值和先前顶点的下标都设置好，起点到起点的权值肯定为0，先前顶点也是自己。然后我们再来个S集合，false表示这个顶点还没有到S集合里面。

        初始化完成之后就是我们最重要的for循环部分的内容了。我们思考一下，我们每次都能找到一个顶点加入到S集合中，那么我们进行n-1次循环不就能保证每个顶点都加入到S中了吗，我们本代码是进行了n次循环是因为我们的S集合是空的，我们并没有先把s顶点加入到S集合里是因为这个操作跟后续顶点都是一样的。

        我们的操作都是先找到路径最短的顶点加入到S集合中，然后进行松弛操作，松弛操作的细节就是对不在S集合中的顶点的路径进行更新，且不要忘记记录这个顶点的先前顶点。

        最短路径生成后我们还需要来一个代码将它打印出来

打印最短路径

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){//找出i顶点的路径vector<int> path;size_t parenti = i;while (parenti != srci){path.push_back(parenti);parenti = pPath[parenti];}path.push_back(srci);reverse(path.begin(), path.end());for (auto p : path){cout << _vertexs[p] << "->";}cout << "权值和：" << dist[i] << endl;}}}

打印最短路径的思路比较简单，我们只需要拿到每个顶点的权值dist，以及它们的先前顶点pPath，我们就可以很好的打印出最短路径的关系，这里的代码大家可以自行理解，因为没有什么难理解的地方。

测试代码

void TestGraphDijkstra()
{const char* str = "syztx";matrix::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> parentPath;g.Dijkstra('s', dist, parentPath);g.PrintShortPath('s', dist, parentPath);
}

运行截图：

1.2 单源最短路径--Bellman-Ford算法

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

我来用大白话通俗的讲一下它的思路，它本质上就是一个暴力更新，我们更新的主要逻辑就是从pPath数组里找出这个顶点的前一个顶点，判断前一个顶点的路径+前一个顶点到本顶点的路径是否小于dist中本顶点的值来进行更新。比如上面这幅图，我们先从s顶点下手的话，我们就是s->s的距离+dist中s的距离，我们会发现s作为我们的起点肯定是一开始就是最小的0，加下来我们再来看从s出去，可以更新两条，s->s+s->t和s->s+s->y，从t和y出去我们又可以更新s->t+t->z和s->y+y->x，接下来再从x出去我们又可以更新s->x+x->t这个时候我们就要对t的前顶点的指向进行更新，总计n轮的更新之后我们肯定就能得到我们要的最短路径了，当然中间我们也可以进行一些优化来帮助我们提前结束循环，我们在代码部分再来细谈。

代码实现

//贝尔曼-福特算法,解决带负权的图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-其他顶点最短路径权值数组dist.resize(n, MAX_W);//vector<int> pPath 记录srci-其他顶点最短路径父顶点数组pPath.resize(n, -1);//先更新srci->srci为缺省值dist[srci] = W();pPath[srci] = 0;for (size_t k = 0; k < n; k++)//总体最多更新n轮{//i->j 更新松弛bool update = false;for (size_t i = 0; i < n; i++){for (size_t j = 0; j < n; j++){//srci-> i + i ->jif (_matrix[i][j] != MAX_W && dist[i] + _matrix[i][j] < dist[j]){update = true;dist[j] = dist[i] + _matrix[i][j];pPath[j] = i;}}}//如果这个轮次中没有更新出更短路径，那么后续轮次就不需要在走了if (update == false) break;}//负权回路for (size_t i = 0; i < n; i++){for (size_t j = 0; j < n; j++){//srci-> i + i ->jif (_matrix[i][j] != MAX_W && dist[i] + _matrix[i][j] < dist[j]){return false;}}}return true;}

我们的形参和前段初始化部分的代码和我们的迪杰斯特拉算法的意思是一样的。我们直接来讲for循环的部分。

        根据我们上面的逻辑分析我们可以得知它要实现最短路径得把每个顶点都处理一遍，所以我们最多是会更新n轮的，我们的具体操作是将srci->i+i->j的路径进行更新，因此我们的if条件就是判断两个顶点是否相连且srci->i+i->j的路径是否小于dist中srci->j的路径。我们的update变量是可以优化这个循环过程的，倘若我们在某一轮中一次更新操作都没有出现，那么我们就可以肯定已经更新完毕了，我们就可以提前退出循环。

        但是我们要对可能出现的负权回路作处理，因为我们的权值实会有负数的，所以我们的图中如果出现了回路，且都为负值，那么理论上就会陷入无限循环的更新，但是我们的代码就只有n轮，所以我们只需要再来一轮，倘若它还能更新，那就是出现了负权回路的情况，我们直接返回false就可以了。

测试代码

void TestGraphBellmanFord()
{const char* str = "syztx";matrix::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;if (g.BellmanFord('s', dist, parentPath)){g.PrintShortPath('s', dist, parentPath);}else{cout << "存在负权回路" << endl;}//微调图结构，带有负权回路的测试const char* str2 = "syztx";matrix::Graph<char, int, INT_MAX, true> g2(str2, strlen(str2));g2.AddEdge('s', 't', 6);g2.AddEdge('s', 'y', 7);g2.AddEdge('y', 'x', -3);g2.AddEdge('y', 'z', 9);g2.AddEdge('y', 'x', -3);g2.AddEdge('y', 's', 1); // 新增g2.AddEdge('z', 's', 2);g2.AddEdge('z', 'x', 7);g2.AddEdge('t', 'x', 5);g2.AddEdge('t', 'y', -8); // 更改g2.AddEdge('t', 'z', -4);g2.AddEdge('x', 't', -2);vector<int> dist2;vector<int> parentPath2;if (g2.BellmanFord('s', dist2, parentPath2)){g2.PrintShortPath('s', dist2, parentPath2);}else{cout << "存在负权回路" << endl;}
}

运行截图：

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

即Floyd算法本质是三维动态规划，D[i][j][k]表示从点i到点j只经过0到k个点最短路径，然后建立起转移方程，然后通过空间优化，优化掉最后一维度，变成一个最短路径的迭代算法，最后即得到所以点的最短路。

翻译成大白话就是我们建两个二维数组，一个用来记录两个顶点的权值，一个用来记录它们的父亲顶点是谁。然后让每个顶点成为中转点来依次更新。

代码实现

//弗洛伊德算法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);}//直接相连的边更新一下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-> {其他顶点} ->jfor (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];//找跟j相连的上一个邻接顶点//如果k->j直接相连，上一个点就是k，vvpPath[k][j]存的就是k//如果k->j没有直接相连，k->...->x->j,vvpPath[k][j]存的就是xvvpPath[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 << vvpPath[i][j] << " ";printf("%3d", vvpPath[i][j]);}cout << endl;}cout << "=================================" << endl;}}

        我们的形参就是连个二维数组，一个是存权值的，一个是存顶点的父亲顶点的。

        我们先对两个二维数组进行初始化，不相连就用MAX_W来表达，没有父亲顶点就用-1来表达，我们的第一步就是对直接相连的边更新一下。接下来我们再来更新经过中转点的情况。我们以k来充当我们的中转点，我们只需要判断i->k是否相连，k->j是否相连，倘若都相连我们就判断一下它们的路径之和是否小于直接相连的路径之和（或则是不相连），是则更新ddist和ppath。这里我们要注意，父亲顶点不能直接写k，因为k是我们的中转点，它不一定是k->j这段路径的j的父亲顶点（找跟j相连的上一个邻接顶点；如果k->j直接相连，上一个点就是k，vvpPath[k][j]存的就是k；如果k->j没有直接相连，k->...->x->j,vvpPath[k][j]存的就是x。

        最后我们可以单独写一个打印将这两张二维表打印出来。

测试代码：

void TestFloydWarShall()
{const char* str = "12345";matrix::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;}
}

运行截图：

我们这里打印出的表的数据比我们的逻辑图少一，因为我们是以下标来当父亲顶点而不是个数。