源最短路径--Bellman-Ford算法四、多源最短路径--Floyd-Warshall算法

一、最短路径

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

二、单源最短路径–Dijkstra算法

v∈Vv∈V的最短路径。

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

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

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

中移出并放入S

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

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

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

代码实现

顶点的下标映射关系std::vectorstd::vectorW

_matrix;

srci){path.push_back(parenti);parenti

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

path.end());for

parentPath);g.PrintShortPath(s,

dist,

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

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

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

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

O(NE)

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

像这里如果我们使用邻接矩阵实现那么遍历所有边的数量的时间复杂度就是O(N^3)这里也可以看出来Bellman-Ford就是一种暴力求解更新。

代码实现

顶点的下标映射关系std::vectorstd::vectorW

_matrix;

srci){path.push_back(parenti);parenti

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

path.end());for

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

MAX_W);//

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

-1);//

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

(update

parentPath))g.PrintShortPath(s,

dist,

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且中间节点属于{12…k-1}取得的一条最短路径。

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

代码实现

顶点的下标映射关系std::vectorstd::vectorW

_matrix;

srci){path.push_back(parenti);parenti

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

path.end());for

FloydWarshall(std::vectorstd::vectorW

vvDist,

_vertexs.size();vvDist.resize(n);vvpPath.resize(n);//

初始化权值和路径矩阵for

没有直接相连k-...-x-jvvpPath[k][j]存就是xvvpPath[i][j]

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

vvDist;std::vectorstd::vectorint

vvParentPath;g.FloydWarshall(vvDist,

vvParentPath);//