单源最短路径问题给定一个图G

v∈Vv∈V的最短路径。

Dijkstra算法就适用于解决带权重的有向图上的单源最短路径问题同时算法要求图中所有边的权重非负。

一般在求解最短路径的时候都是已知一个起点和一个终点所以使用Dijkstra算法求解过后也就得到了所需起点到终点的最短路径。

针对一个带权有向图G将所有结点分为两组S和QS是已经确定最短路径的结点集合在初始时为空初始时就可以将源节点s放入毕竟源节点到自己的代价是0Q

中移出并放入S

为空即所有节点都已经查找过一遍并确定了最短路径至于一些起点到达不了的结点在算法循环后其代价仍为初始设定的值不发生变化。

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

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

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

代码实现

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

这也就是我们这两个形参的意思第一个新参就是起点。

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

然后我们再来个S集合false表示这个顶点还没有到S集合里面。

初始化完成之后就是我们最重要的for循环部分的内容了。

我们思考一下我们每次都能找到一个顶点加入到S集合中那么我们进行n-1次循环不就能保证每个顶点都加入到S中了吗我们本代码是进行了n次循环是因为我们的S集合是空的我们并没有先把s顶点加入到S集合里是因为这个操作跟后续顶点都是一样的。

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

打印最短路径

srci){path.push_back(parenti);parenti

pPath[parenti];}path.push_back(srci);reverse(path.begin(),

path.end());for

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

测试代码

parentPath);g.PrintShortPath(s,

dist,

Dijkstra算法只能用来解决正权图的单源最短路径问题但有些题目会出现负权图。

这时这个算法就不能帮助我们解决问题了而bellman—ford算法可以解决负权图的单源最短路径问题。

它的优点是可以解决有负权边的单源最短路径问题而且可以用来判断是否有负权回路。

它也有明显的缺点它的时间复杂度

O(N*E)

(N是点数E是边数)普遍是要高于Dijkstra算法O(N²)的。

像这里如果我们使用邻接矩阵实现那么遍历所有边的数量的时间复杂度就是O(N^3)这里也可以看出

我来用大白话通俗的讲一下它的思路它本质上就是一个暴力更新我们更新的主要逻辑就是从pPath数组里找出这个顶点的前一个顶点判断前一个顶点的路径前一个顶点到本顶点的路径是否小于dist中本顶点的值来进行更新。

比如上面这幅图我们先从s顶点下手的话我们就是s-s的距离dist中s的距离我们会发现s作为我们的起点肯定是一开始就是最小的0加下来我们再来看从s出去可以更新两条s-ss-t和s-ss-y从t和y出去我们又可以更新s-tt-z和s-yy-x接下来再从x出去我们又可以更新s-xx-t这个时候我们就要对t的前顶点的指向进行更新总计n轮的更新之后我们肯定就能得到我们要的最短路径了当然中间我们也可以进行一些优化来帮助我们提前结束循环我们在代码部分再来细谈。

代码实现

dist,记录srci-其他顶点最短路径权值数组dist.resize(n,

MAX_W);//vectorint

记录srci-其他顶点最短路径父顶点数组pPath.resize(n,

-1);//先更新srci-srci为缺省值dist[srci]

W();pPath[srci]

i;}}}//如果这个轮次中没有更新出更短路径那么后续轮次就不需要在走了if

(update

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

我们直接来讲for循环的部分。

根据我们上面的逻辑分析我们可以得知它要实现最短路径得把每个顶点都处理一遍所以我们最多是会更新n轮的我们的具体操作是将srci-ii-j的路径进行更新因此我们的if条件就是判断两个顶点是否相连且srci-ii-j的路径是否小于dist中srci-j的路径。

我们的update变量是可以优化这个循环过程的倘若我们在某一轮中一次更新操作都没有出现那么我们就可以肯定已经更新完毕了我们就可以提前退出循环。

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

测试代码

parentPath)){g.PrintShortPath(s,

dist,

parentPath2)){g2.PrintShortPath(s,

dist2,

Floyd-Warshall算法是解决任意两点间的最短路径的一种算法。

Floyd算法考虑的是一条最短路径的中间节点即简单路径p{v1,v2,…,vn}上除v1和vn的任意节点。

设k是p的一个中间节点那么从i到j的最短路径p就被分成i到k和k到j的两段最短路径p1p2。

p1

是从i到k且中间节点属于{12…k-1}取得的一条最短路径。

p2是从k到j且中间节点属于{1

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

翻译成大白话就是我们建两个二维数组一个用来记录两个顶点的权值一个用来记录它们的父亲顶点是谁。

然后让每个顶点成为中转点来依次更新。

代码实现

_vertexs.size();vvDist.resize(n);vvpPath.resize(n);//初始化权值和路径矩阵for

(size_t

vvDist[k][j];//找跟j相连的上一个邻接顶点//如果k-j直接相连上一个点就是kvvpPath[k][j]存的就是k//如果k-j没有直接相连k-...-x-j,vvpPath[k][j]存的就是xvvpPath[i][j]

vvpPath[k][j];}}}//

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

我们先对两个二维数组进行初始化不相连就用MAX_W来表达没有父亲顶点就用-1来表达我们的第一步就是对直接相连的边更新一下。

接下来我们再来更新经过中转点的情况。

我们以k来充当我们的中转点我们只需要判断i-k是否相连k-j是否相连倘若都相连我们就判断一下它们的路径之和是否小于直接相连的路径之和或则是不相连是则更新ddist和ppath。

这里我们要注意父亲顶点不能直接写k因为k是我们的中转点它不一定是k-j这段路径的j的父亲顶点找跟j相连的上一个邻接顶点如果k-j直接相连上一个点就是kvvpPath[k][j]存的就是k如果k-j没有直接相连k-...-x-j,vvpPath[k][j]存的就是x。

测试代码

vvParentPath;g.FloydWarShall(vvDist,

vvParentPath);//

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