目录
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; // 顶点到下标的映射};
}