欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 新闻 > 会展 > 图论 —— 求解最短路径(Dijkstra算法、Bellman-Ford算法、Floyd-Warshall算法)

图论 —— 求解最短路径(Dijkstra算法、Bellman-Ford算法、Floyd-Warshall算法)

2024/12/22 0:55:42 来源:https://blog.csdn.net/D5486789_/article/details/144401964  浏览:    关键词:图论 —— 求解最短路径(Dijkstra算法、Bellman-Ford算法、Floyd-Warshall算法)

目录

1.最短路径

认识最短路径

最短路径的分类

2.单源最短路径

Dijkstra算法

Dijkstra算法的大致思想

Dijkstra算法的大致流程图

Dijkstra算法代码如下

Dijkstra算法的缺陷

Bellman-Ford算法

Bellman-Ford算法的大致思想

Bellman-Ford算法的大致流程

Bellman-Ford算法代码如下

Bellman-Ford算法的优缺点

3.多源最短路径

Floyd-Warshall算法

Floyd-Warshall算法的大致思想

Floyd-Warshall算法的大致流程图

Floyd-Warshall算法的代码


1.最短路径

认识最短路径

在现实生活中,我们当我们想要去其他地方的时候,而到达目的地的交通方式往往不止一种,我们往往会计算到达目的地的各种交通方式所花费的成本,计算成本不是目的,我们的目的是选择交通成本最小的路径,为了解决这种问题,就可以使用图论中的求解最短路径的算法 —— Dijkstra算法、Bellman-Ford算法、Floyd-Warshall算法。其中,前两个是计算单源最短路径的算法,最后一个是计算多源最短路径的算法。

那什么是最短路径呢?最短路径就是从一点出发到达另一点的权值之和最小的路径。

比如在下面这个图中,我们想要从s点出发到达x点,我们有多条路径可以选择,比如:

  • s->t->x  路径上的权值和为:11
  • s->y->x  路径上的权值和为:14
  • s->y->z->x  路径上的权值和为:13
  • s->y->t->x  路径上的权值和为:9

我没有枚举所有情况,但是我们应该可以看出s到x的权值和最小是9,路径为s->y->t->x,这条路径就是最短路径。

最短路径的分类

最短路径问题分为单源最短路径问题和多源最短路径问题。

  • 单源最短路径求解的是从图中的一个顶点出发,到达图中所有顶点的最短路径
  • 多源最短路径求解的是同一个图中,任意两个顶点之间的最短路径

求解单源最短路径的算法有Dijkstra算法(迪杰斯特拉算法)、Bellman-Ford算法(贝尔曼福特),求解多源最短路径的算法有Floyd-Warshall算法(弗洛伊德算法)。

2.单源最短路径

Dijkstra算法

Dijkstra算法的大致思想

将图G中的顶点分为两组,S和Q,S是已经确定最短路径的顶点集合,Q是还没有确定最短路径的顶点的集合,每次选择从集合S到集合Q中的权值最小的边,并将这条边的终点u从集合Q中移除并添加到集合S中,然后对u的每一个相邻顶点v进行松弛操作(贪心策略),直到集合Q中没有结点为止;松弛操作就是对每一个相邻顶点v,判断源结点s到u的代价和u到v的代价和是否小于原来的s到v的代价,将s到v的代价更新为两者中较小的那个。

  • 注意:终点是不在集合S中的点。

我们可以分析一下贪心策略:每次选择集合S到集合Q中权值最小的边,这条边的起点在S中,终点在Q中,我们假设这条边的起点是start,终点是end,源结点为s;因为集合S是已经确定最短路径的顶点,那意味着s到start的代价是最小的,边(start,end)的权值也是最小的,两个最小相加就意味着s到end的代价是最小的。

  • s到end代价最小的路径是s->start2->end,代价和为4。 

Dijkstra算法的大致流程图

  • 图中的**表示无穷大

最终,以顶点s为起始原点到达图中的所有顶点的最短路径如下:

  • s->s = 0
  • s->y = s->s->y = 0+5 = 5
  • s->z = s->s->y->z = 0+5+2 = 7
  • s->t = s->s->y->t = 0+5+3 = 8
  • s->x = s->s->y->t->x = 0+5+3+1 = 9

Dijkstra算法代码如下

#include <vector>
#include <map>// 邻接矩阵存储的图
namespace Link_Matrix
{/** V: 顶点的类型* W: 权值的类型* MAX_VAL: 权值的最大值,表示两个顶点之间没有关系,默认是int的最大值* Direction: 表示该图为有向图还是无向图,默认是无向图*/template<class V, class W, W MAX_VAL = INT_MAX, bool Direction = false>class Graph{using Self = Graph<V, W, MAX_VAL, Direction>;public:/*********************************图的基础操作***********************************/// 默认构造函数Graph() = default;// 构造函数Graph(const V* arr, size_t n){// 把所有的顶点存储起来,并将顶点和顶点的下标建立映射关系,相当于为顶点编号_vertexs.reserve(n);for (int i = 0; i < n; ++i){_vertexs.push_back(arr[i]);_indexMap[arr[i]] = i;}// 为邻接矩阵开辟空间,并全部初始化为MAX_VAL,用于后续手动添加边_matrix.resize(n);for (int i = 0; i < _matrix.size(); ++i){_matrix[i].resize(n, MAX_VAL);}}// 获取顶点的索引size_t GetVertexIndex(const V& vertex){auto it = _indexMap.find(vertex);if (it != _indexMap.end()) // 找到了对应的顶点{return it->second;}else                       // 该顶点不存在{throw invalid_argument("顶点不存在");return -1;}}// 添加边void AddEdge(const V& src, const V& dst, const W& w){size_t srci = GetVertexIndex(src);size_t dsti = GetVertexIndex(dst);_matrix[srci][dsti] = w;// 如果该图为无向图,对称的位置也要添加对应的权值if (Direction == false){_matrix[dsti][srci] = w;}}void AddEdge(size_t srci, size_t dsti, const W& w){_matrix[srci][dsti] = w;// 如果该图为无向图,对称的位置也要添加对应的权值if (Direction == false){_matrix[dsti][srci] = w;}}/** Dijkstra算法* src: 起始源点* min_dist: 记录起始源点到图中每个点的距离,不断跟新出最短路径(输出型参数)* pPath: 记录最终结果,pPath[i]表示s->i的最短路径中,i的上一个结点(输出型参数)* 无返回值*/void Dijkstra(const V& src, std::vector<W>& dist, std::vector<int>& pPath){size_t srci = GetVertexIndex(src); // 将顶点转化为对应的下标,便于操作int n = _vertexs.size();// 初始化工作dist.resize(n, MAX_VAL);pPath.resize(n, -1);dist[srci] = 0;pPath[srci] = srci;// 集合S,不在S集合中就在Q集合中 std::vector<bool> S(n, false);// 有n个顶点,选n次for (size_t j = 0; j < n; ++j){// 选出最短路径的终点uint min = MAX_VAL;int u = 0;for (int i = 0; i < n; ++i){if (S[i] == false && dist[i] < min){u = i;min = dist[i];}}S[u] = true;// 松弛更新u连接的顶点vfor (int v = 0; v < n; ++v){// 顶点v不在集合S中,u和v之间有边,并且(srci->u) + (u->v) < (srci->v)则更新if (S[v] == false && _matrix[u][v] != MAX_VAL && dist[u] + _matrix[u][v] < dist[v]){dist[v] = dist[u] + _matrix[u][v];  // 更新s->v的距离pPath[v] = u;                       // 更新v的上一个结点}}}}private:std::vector<V> _vertexs;             // 顶点的集合std::vector<std::vector<W>> _matrix; // 邻接矩阵std::map<V, int> _indexMap;          // 顶点到下标的映射};
}

Dijkstra算法的缺陷

Dijkstra算法存在的问题是不支持图中带负权路径,如果带有负权路径,则可能会找不到一些路径的最短路径 。

我们以下面这个图为例:以s为起始源点

运行结果如下:

可以看到s到x的最短路径没有更新出来,这是因为负权边的存在可能会导致Dijkstra算法的贪心策略失效。这是为什么呢?

如下图:

  •  当我们选择权值为-7的边的终点进行松弛操作的时候,无法将权值-7计算在最短路径中,从而导致贪心策略失效。

Bellman-Ford算法

Dijkstra算法只能解决正权图单源最短路径问题,但有些场景会出现负权图,Dijkstra算法无法解决,于是,有大佬发明了可以解决带负权的图的最短路径问题。

Bellman-Ford算法的大致思想

进行多轮更新,每一轮更新都要处理所有的边,最多更新n轮(n是图中的顶点个数)。

  • 你肯定有疑问,为什么要更新n轮?这是因为,每一轮更新都要更新所有的边,但是由于遍历边的顺序可能导致原先需要改变的边没有改变,这个时候就需要再次更新就纠正了,所以我们最多需要跟新n次,相当于每次都能确定一个顶点的最短路径。

在Dijkstra算法的缺陷中,我们分析了为什么Dijkstra算法无法解决带负权的图的最短路径问题,其实就是不能将负权计算在路径中,说的通俗一点就是没有访问到,这一点和Dijkstra算法的松弛操作有关;于是,Bellman-Ford算法采用更加暴力的遍历方式,每一次的松弛操作都对所有的边进行更新。

Bellman-Ford算法的大致流程

下面图片摘自《算法导论》

Bellman-Ford算法代码如下

#include <vector>
#include <map>// 邻接矩阵存储的图
namespace Link_Matrix
{/** V: 顶点的类型* W: 权值的类型* MAX_VAL: 权值的最大值,表示两个顶点之间没有关系,默认是int的最大值* Direction: 表示该图为有向图还是无向图,默认是无向图*/template<class V, class W, W MAX_VAL = INT_MAX, bool Direction = false>class Graph{public:/*********************************图的基础操作***********************************/// 默认构造函数Graph() = default;// 构造函数Graph(const V* arr, size_t n){// 把所有的顶点存储起来,并将顶点和顶点的下标建立映射关系,相当于为顶点编号_vertexs.reserve(n);for (int i = 0; i < n; ++i){_vertexs.push_back(arr[i]);_indexMap[arr[i]] = i;}// 为邻接矩阵开辟空间,并全部初始化为MAX_VAL,用于后续手动添加边_matrix.resize(n);for (int i = 0; i < _matrix.size(); ++i){_matrix[i].resize(n, MAX_VAL);}}// 获取顶点的索引size_t GetVertexIndex(const V& vertex){auto it = _indexMap.find(vertex);if (it != _indexMap.end()) // 找到了对应的顶点{return it->second;}else                       // 该顶点不存在{throw invalid_argument("顶点不存在");return -1;}}// 添加边void AddEdge(const V& src, const V& dst, const W& w){size_t srci = GetVertexIndex(src);size_t dsti = GetVertexIndex(dst);_matrix[srci][dsti] = w;// 如果该图为无向图,对称的位置也要添加对应的权值if (Direction == false){_matrix[dsti][srci] = w;}}void AddEdge(size_t srci, size_t dsti, const W& w){_matrix[srci][dsti] = w;// 如果该图为无向图,对称的位置也要添加对应的权值if (Direction == false){_matrix[dsti][srci] = w;}}/** BellmanFord算法* min_dist: 记录起始源点到图中每个点的距离,不断跟新出最短路径(输出型参数)* pPath: 记录最终结果,pPath[i]表示s->i的最短路径中,i的上一个结点(输出型参数)* 如果能生成最短路径就返回true,否则返回false*/bool BellmanFord(const V& src, std::vector<W>& dist, std::vector<int>& pPath){// 初始化工作操作int srci = GetVertexIndex(src);int n = _vertexs.size();dist.resize(n, MAX_VAL);pPath.resize(n, -1);dist[srci] = W();// 最多进行n轮跟新for (int k = 0; k < n; ++k){// flag为本轮更新是否更新的标记bool flag = false;// 遍历所有的边for (int i = 0; i < n; ++i){for (int j = 0; j < n; ++j){// 如果两个点之间有边,并且 (srci->i)+(i->j) < (srci->j) 则更新 if (_matrix[i][j] != MAX_VAL && dist[i] + _matrix[i][j] < dist[j]){dist[j] = dist[i] + _matrix[i][j];pPath[j] = i;flag = true;}}}// 如果本轮更新未更新任何值,说明后面也不会再更新了,直接退出即可if (flag == false)break;}// 判断是否带负权回路for (int i = 0; i < n; ++i){for (int j = 0; j < n; ++j){// 如果两个点之间有边,并且 (srci->i)+(i->j) < (srci->j) 则更新 if (_matrix[i][j] != MAX_VAL && dist[i] + _matrix[i][j] < dist[j]){return false; // 如果还能更新说明带负权回路,神仙难救}}}return true;}private:std::vector<V> _vertexs;             // 顶点的集合std::vector<std::vector<W>> _matrix; // 邻接矩阵std::map<V, int> _indexMap;          // 顶点到下标的映射};
}

Bellman-Ford算法的优缺点

缺点:该算法采用更加暴力的松弛操作方式,遍历的时间复杂度为O(n),最多需要进行n轮,所以,总体的时间复杂度为O(n^3),要普遍高于Dijkstra算法的O(n^2),空间复杂度为O(n),算法的效率会慢一点。

优点:Bellman-Ford算法能够解决带负权的图的最短路径问题,而且能够判断是否存在负权回路。

3.多源最短路径

Floyd-Warshall算法

Floyd-Warshall算法的大致思想

  • 依次取每个点作为中间点更新所有点之间的最短路径。

Floyd-Warshall算法的大致流程图

Floyd-Warshall算法的代码

#include <vector>
#include <map>// 邻接矩阵存储的图
namespace Link_Matrix
{/** V: 顶点的类型* W: 权值的类型* MAX_VAL: 权值的最大值,表示两个顶点之间没有关系,默认是int的最大值* Direction: 表示该图为有向图还是无向图,默认是无向图*/template<class V, class W, W MAX_VAL = INT_MAX, bool Direction = false>class Graph{public:// 默认构造函数Graph() = default;// 构造函数Graph(const V* arr, size_t n){// 把所有的顶点存储起来,并将顶点和顶点的下标建立映射关系,相当于为顶点编号_vertexs.reserve(n);for (int i = 0; i < n; ++i){_vertexs.push_back(arr[i]);_indexMap[arr[i]] = i;}// 为邻接矩阵开辟空间,并全部初始化为MAX_VAL,用于后续手动添加边_matrix.resize(n);for (int i = 0; i < _matrix.size(); ++i){_matrix[i].resize(n, MAX_VAL);}}// 获取顶点的索引size_t GetVertexIndex(const V& vertex){auto it = _indexMap.find(vertex);if (it != _indexMap.end()) // 找到了对应的顶点{return it->second;}else                       // 该顶点不存在{throw invalid_argument("顶点不存在");return -1;}}// 添加边void AddEdge(const V& src, const V& dst, const W& w){size_t srci = GetVertexIndex(src);size_t dsti = GetVertexIndex(dst);_matrix[srci][dsti] = w;// 如果该图为无向图,对称的位置也要添加对应的权值if (Direction == false){_matrix[dsti][srci] = w;}}void AddEdge(size_t srci, size_t dsti, const W& w){_matrix[srci][dsti] = w;// 如果该图为无向图,对称的位置也要添加对应的权值if (Direction == false){_matrix[dsti][srci] = w;}}/***********************************多源最短路径********************************//** 弗洛伊德算法* vvDist和vvpPath都是输出型参数* vvDist:存储两个点之间的最短路径的权值* vvpPath:vvpPath[i][j]表示i到j的路径中,j的上一个顶点,用于后续的打印操作* 我们前面的单源最短路径中,采用一维数组存储最短路径* 现在,要求每两个点之间的最短路径,可以理解为把单源最短路径走n次* 所以需要用二维矩阵存储相关信息*/void FloydWarshall(std::vector<std::vector<W>>& vvDist, std::vector<std::vector<int>>& vvpPath){int n = _vertexs.size();// 完成初始化工作vvDist.resize(n);vvpPath.resize(n);for (int i = 0; i < n; ++i){vvDist[i].resize(n, MAX_VAL);vvpPath[i].resize(n, -1);}// 先把直接相连的边更新一下for (int i = 0; i < n; ++i){for (int j = 0; j < n; ++j){if (_matrix[i][j] != MAX_VAL){vvDist[i][j] = _matrix[i][j];vvpPath[i][j] = i;}if (i == j){vvDist[i][j] = 0;}}}// 依次将每个点作为中间点去更新每两个点之间的最短路径for (int k = 0; k < n; ++k){for (int i = 0; i < n; ++i){for (int j = 0; j < n; ++j){if (vvDist[i][k] != MAX_VAL && vvDist[k][j] != MAX_VAL&& vvDist[i][k] + vvDist[k][j] < vvDist[i][j]){vvDist[i][j] = vvDist[i][k] + vvDist[k][j];/**  找跟j相连的上一个顶点*  如果k->j直接相连,j的上一个点就是k,vvpPath[k][j] = k。*  如果没有直接相连,k->x->j,vvpPath[k][j] = vvpPath[x][j]*/vvpPath[i][j] = vvpPath[k][j];}}}}}private:std::vector<V> _vertexs;             // 顶点的集合std::vector<std::vector<W>> _matrix; // 邻接矩阵std::map<V, int> _indexMap;          // 顶点到下标的映射};
}

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com