nike官方网站定制,做旅游网站需要的背景,长春火车站是南站还是北站,连锁店进销存管理软件文章目录 1. 最短路径问题2. 单源最短路径--Dijkstra算法算法思想图解如何存储路径及其权值代码实现调式观察打印最短路径Dijkstra算法的缺陷 3. 源码 1. 最短路径问题
最短路径问题#xff1a; 从带权有向图#xff08;求最短路径通常是有向图#xff09;G中的某一顶点出发… 文章目录 1. 最短路径问题2. 单源最短路径--Dijkstra算法算法思想图解如何存储路径及其权值代码实现调式观察打印最短路径Dijkstra算法的缺陷 3. 源码 1. 最短路径问题
最短路径问题 从带权有向图求最短路径通常是有向图G中的某一顶点出发找出一条通往另一顶点的最短路径最短也就是沿路径各边的权值总和达到最小。 那下面我们就要来学习几个求最短路径的算法
2. 单源最短路径–Dijkstra算法
这篇文章我们先来学习第一个求单源最短路径的算法——迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959年提出的然后后面我们还会学到求多源最短路径的算法。
所以这里先给大家介绍一下什么是单源最短路径什么是多源最短路径 单源最短路径指的是从一个源节点出发计算到其他所有节点的最短路径。也就是说在单源最短路径问题中只需要确定一个起点然后计算该起点到图中所有其他节点的最短距离。 多源最短路径则是在图中计算任意两个节点之间的最短路径。换言之需要求解所有可能的起点和终点之间的最短路径。 那下面我们就来学习一下第一个求单源最短路径的算法——Dijkstra算法
算法思想
首先我们可以先从概念上了解一下Dijkstra算法的思想 单源最短路径问题给定一个图G ( V E ) 求源结点s ∈ V 到图中每个结点v ∈ V的最短路径。Dijkstra算法就适用于解决带权重的有向图上的单源最短路径问题同时算法要求图中所有边的权重非负。一般在求解最短路径的时候都是已知一个起点和一个终点所以使用Dijkstra算法求解过后也就得到了所需起点到终点的最短路径。 针对一个带权有向图G将所有结点分为两组S和QS是已经确定最短路径的结点集合在初始时为空初始时就可以将源节点s放入毕竟源节点到自己的代价是0Q 为其余未确定最短路径的结点集合每次从Q 中找出一个从起点到该结点代价最小的结点u 将u 从Q 中移出并放入S 中对u 的每一个相邻结点v 且v不在S中进行松弛操作。松弛即对每一个相邻结点v 判断源节点s到结点u 的代价与u 到v 的代价之和是否比原来s 到v 的代价更小若代价比原来小则要将s 到v 的代价更新为s 到u 与u 到v 的代价之和否则维持原样。如此一直循环直至集合Q 为空即所有节点都已经查找过一遍并确定了最短路径至于一些起点到达不了的结点在算法循环后其代价仍为初始设定的值不发生变化。 Dijkstra算法每次都是选择V-S中最小的路径节点来进行更新并加入S中所以该算法使用的是贪心策略。 Dijkstra算法存在的问题是不支持图中带负权路径如果带有负权路径则可能会找不到一些路径的最短路径这个我们后面也会给大家演示。
图解
那只看上面的概念的话大家可能还不是特别理解那下面我们来画图带大家分析一下
首先我们可以先来看一下算法导论上给出的图解 大家可以自己先看一下 然后我来带大家走一遍这个过程 其实就按照上面的思想一步步走就行了。 按照上面说的将所有结点分为两组S和QS是已经确定最短路径的结点集合Q 为其余未确定最短路径的结点集合。 那起始的时候可以认为S是空的所有结点都在Q里面。 然后这里选择的起点是s 每次从Q 中找出一个从起点到该结点代价最小的结点u那第一次这个结点u就是s可以认为s到s的距离是0图中每个结点里面的值就表示当前从起点到自己的最短路径还没更新的路径用∞标识那把s结点放到S集合里面Q中删去s 然后对s 的每一个相邻结点v 进行松弛操作其实去更新起点到它相邻点的距离s到它相邻的两个结点距离s-t为10s-y为5都比原来从起点到它们的距离小所以更新 然后再从Q里面找一个到起点路径最短的点那这次找到的是y此时s-y为5是最小的把y从Q中移除放入S里面 然后对y进行松弛操作 y相邻的几个顶点到y的距离y到起点s的距离都比之前起点到它们的距离短所以都更新 接着继续从Q中选一个到起点距离最短的是zz从Q中移出放入S 接着对x进行松弛操作更新相应的距离 接着继续从Q中选一个到起点距离最短的是tt从Q中移出放入S 接着对t进行松弛操作更新相应的距离 再接着继续从Q中选一个到起点距离最短的是xx从Q中移出放入S 接着再对x进行松弛操作 至此集合Q 为空起始Q是满的所以n个结点的话其实就选了n次去更新即所有节点都已经查找过一遍并确定了最短路径 算法执行结束 如何存储路径及其权值
相信算法现在大家已经理解了但是还有一些问题需要我们解决 既然我们是要求最短路径那肯定得把相关的信息存储起来啊上面图中直接把每个顶点对应最短路径的权值直接写到了结点里面而且每条路径是怎么走的经过了哪些顶点我们也很容易看出来。 可是后面我们要写代码那在写代码的时候我们如何把这些信息也存储起来呢 是这样处理的 因为每个顶点不是都映射一个下标嘛所以我们就可以搞一个数组每个下标映射的顶点是谁这个位置就存储起点到这个顶点的最短路径。 那最开始就是这样的 然后后面我们每次更新最短路径的时候修改里面的权值就行了 那上面存的是最短路径的权值那路径又要如何存储呢 一条路径可能会经过多个顶点啊。 那这里呢还是用一个一维数组就可以搞定 怎么做呢 很简单每个顶点映射的位置存储路径上在它前面的那个顶点映射的下标如果把路径看成一棵树的话就是存储它的父结点的下标 比如最开始就可以这样存 首先s自己就是起点可以认为最短路径就是s-s所以它存自己的下标然后剩下的顶点都还没有更新最短路径起始存一个-1 接着每走一步就去更新数组就行了存路径上它前面的那个结点可以认为是它的父结点的下标类似并查集那里用的双亲表示法存储那到最后的时候就是这样的 那这样存储路径的话我们想要获取一个顶点的最短路径的时候就从这个顶点开始顺序它的父亲路径中的上一个结点往上找就行了找到起点停止就是一条完整的路径类似并查集里面的findRoot顺着父结点向上找根。 代码实现
那下面我们就来实现一下代码 首先需要给一个起点然后两个vector存储最短路径及对应的路径权值 然后按照我们上面分析的思路走就行了 注释写的比较清楚相信大家应该很容易可以看懂说一点就是我们现在用的是邻接矩阵结构所有查找u相邻的结点是去邻接矩阵_matrix里面找如果下标[u][v]的位置对应的权值不是MAX_W那它们就相连的v就是u的一个相邻顶点然后再判断如果源节点s到结点u 的代价与u 到v 的代价之和其实就是距离嘛是否比原来s 到v 的代价更小若代价比原来小则要将s 到v 的代价更新为s 到u 与u 到v 的代价之和更新距离 调式观察
那这就实现好了我们可以先通过调式观察一下 我这里已经写好了一个测试用例最后会给大家分享源码这个图就是我们上面讲解思想的时候对应的那个图 我们来调式观察一下 对比一下我们之前分析的 没有问题一模一样 打印最短路径
那下面呢我们可以写一个大于路径的函数把最终得到的起点到各顶点的最短路径以及权值都打印出来看一下和上面图上的是否一样 那我们拿到这两个数组就可以去打印 但是这里打印的时候有一个问题 按我们上面说的找路径的时候通过pPath数组顺着结点的父亲或者说它的路径上的前一个结点往上找就行了找到起点停止。 但是 这样找出来的路径是不是反的啊因为我们最后找到的是起点而正常情况应该是从起点开始嘛。 所以我们要处理一下也很好搞 我们可以搞一个vector把路径上的结点保存下来然后逆置一下再去打印就行了 来实现一下 然后我们来打印一下看看 大家可以对照一下没有问题 Dijkstra算法的缺陷
但是呢Dijkstra算法是有一些缺陷的对于带有负权值的边的图Dijkstra算法是搞不定的
这里呢也准备了一个测试用例我们可以来看一下 首先它对应的一个图应该是这样的 那我们现在对这个图执行Dijkstra算法并打印出来看一下 是这样一个结果 但是我们会发现如果按照这个图有负权值的话其实有一条最短路径其实没有更新出来s-t-y应该是310-73 也就是说3应该是起点s到y的最短距离s-t-y是最短路径。 图中带有负权路径时贪心策略就失效了。 那为什么会这样呢 因为按照Dijkstra算法的话 这里起点是s所以第一次选到s放到S集合里面然后对s的相邻顶点进行松弛操作更新距离s-t为10s-y为5所以第二次选到y那y就被放到S集合里面了而S是已经确定最短路径的结点集合所以它这里的贪心策略就认为此时的5就是s-y的最短路径距离了当然如果没有负权值的话这样是肯定正确的y的最短路径已经确定了。 所以后面再去对t的相邻顶点进行松弛的时候就不会判断stty的距离是否小于sy也不会再更新y的最短路径了所以上面s-t-y就没有更新出来。因为每次都是从Q里面选的而y前面已经放到S集合里面了。 但是有了负权值的话sy的最短路径就不一定是5了如果全是正的话肯定没问题后面绕到其它的路径如果遇到负权值就可能会比5还小。 所以对于有负权值的图Dijkstra算法就不再适用这种贪心策略就失效了。
那对于有负权值的图我们如何求最短路径呢 bellman—ford算法可以解决负权图的单源最短路径问题 这个我们下一篇文章就会讲到…
3. 源码
void Dijkstra(const V src, vectorint pPath, vectorW dist)
{//初始化一下记录路径和权值距离的数组size_t srci GetVertexIndex(src);size_t n _vertexs.size();pPath.resize(n, -1);dist.resize(n, MAX_W);//集合S为已确定最短路径的顶点集合这里我们用一个数组表示S集合就可以//初始化全falseS中无结点表示所有顶点都在Q中//不在S就在Q其余未确定最短路径的结点集合vectorbool s(n, false);pPath[srci] srci;dist[srci] 0;//n个结点需要选择n次去更新路径for (size_t i 0; i n; i){int u 0;W minDist MAX_W;//从Q 中找出一个从起点到该结点代价最小的结点ufor (size_t j 0; j n; j){if (s[i] false dist[i] minDist){u i;minDist dist[i];}}//将u 从Q 中移出并放入S 中s[u] true;//对u 的每一个相邻结点v 进行松弛操作如果src-u u-v src-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];//同时更新记录路径的数组pPathpPath[v] u;}}}}void ptintMinPath(const V src, const vectorint pPath, const vectorW dist)
{size_t srci GetVertexIndex(src);size_t n _vertexs.size();for (size_t i 0; i n; i){if (i ! srci)//起点-》起点就没必要打印了{//定义一个vector保存路径上的结点vectorint path;//从当前结点开始顺着父结点往上走size_t parenti i;while (parenti ! srci){path.push_back(parenti);parenti pPath[parenti];}path.push_back(srci);//逆置path数组reverse(path.begin(), path.end());//打印路径for (auto e : path){cout _vertexs[e] -;}//打印权值cout dist[i] endl;}}
}void TestGraphDijkstra()
{/*const char* str syztx;Graphchar, 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);vectorint dist;vectorint pPath;g.Dijkstra(s, dist, pPath);g.ptintMinPath(s, dist, pPath);*/// 图中带有负权路径时贪心策略则失效了。// 测试结果可以看到s-t-y之间的最短路径没更新出来const char* str sytx;Graphchar, 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);vectorint dist;vectorint pPath;g.Dijkstra(s, dist, pPath);g.ptintMinPath(s, dist, pPath);
}
