品牌网站建设1毛尖,ip设计,免费咨询的英文,长沙开福区专业制作网站文章目录 前言一、Dijkstra#xff08;迪克斯特拉#xff09;1.方法#xff1a;2.代码实现 二、FloydWarshall#xff08;弗洛伊德#xff09;1.方法2.代码实现 完整源码 前言
最短路径问题#xff1a;从在带权有向图G中的某一顶点出发#xff0c;找出一条通往另一顶点… 文章目录 前言一、Dijkstra迪克斯特拉1.方法2.代码实现 二、FloydWarshall弗洛伊德1.方法2.代码实现 完整源码 前言
最短路径问题从在带权有向图G中的某一顶点出发找出一条通往另一顶点的最短路径最短也就是沿路径各边的权值总和达到最小。 单源最短路径问题给定一个图G ( V E ) G(VE)G(VE)求源结点s ∈ V s∈Vs∈V到图 中每个结点v ∈ V v∈Vv∈V的最短路径
一、Dijkstra迪克斯特拉
1.方法
针对一个带权有向图G将所有结点分为两组S和QS是已经确定最短路径的结点集合在初始时 为空初始时就可以将源节点s放入毕竟源节点到自己的代价是0Q 为其余未确定最短路径 的结点集合每次从Q 中找出一个起点到该结点代价最小的结点u 将u 从Q 中移出并放入S 中对u 的每一个相邻结点v 进行松弛操作。松弛即对每一个相邻结点v 判断源节点s到结点u 的代价与u 到v 的代价之和是否比原来s 到v 的代价更小若代价比原来小则要将s 到v 的代价更新 为s 到u 与u 到v 的代价之和否则维持原样。如此一直循环直至集合Q 为空即所有节点都已经 查找过一遍并确定了最短路径 Dijkstra算法每次都是选择V-S中最小的路径节点来进行更新并加入S中所以该算法使用的是贪心策略。
核心就是从当前选入的顶点当中去找其直接相连的最小的边然后用这个最小边相连的另一个顶点为起点找与其直接相连边中最小的边eg与s直接相连的为ty。最小的边为5即y顶点其为s到y的最短距离然后以y为起点与y直接相连的有txz。最小的边为2即z点y到z最短为2所以s到z最短为7以此类推直到所有点都被当过起点后结束
2.代码实现
void Dijkstra(const V src, vectorW dist, vectorint pPath){//dist存的src到其他点的最短路径// vectorint pPath 记录srci-其他顶点最短路径父顶点数组size_t srci GetVertexIndex(src);size_t n _vertexs.size();dist.resize(n, MAX_W);pPath.resize(n, -1);dist[srci] 0;//自己到自己距离为0pPath[srci] srci;// 已经确定最短路径的顶点集合vectorbool S(n, false);for (size_t j 0; j n; j){int u srci;//u为当前最短路径顶点W min MAX_W;//min为起始点到u的距离for (size_t i 0; i n; i){if (S[i] false dist[i] min){u i;min dist[i];}}//找到与当前起始点直接相连的最短路径的顶点后//将其位置置为true表明已经选入S[u] true;// 松弛算法更新一遍u连接的所有边看是否能更新出更短连接路径for (size_t v 0; v n; v){// 如果srci-u u-k 比 srci-k更短 则进行更新if (S[v] false _matrix[u][v] ! MAX_W dist[u] _matrix[u][v] dist[v]){dist[v] dist[u] _matrix[u][v];pPath[v] u;}}}}//打印路径
void PrintShortPath(const V src, const vectorW dist, const vectorint pPath) {size_t srci GetVertexIndex(src);size_t n _vertexs.size();for (size_t i 0; i n; i) {if (i ! srci) {vectorintpath;//path为src到其他顶点路径size_t parenti i;while (parenti ! srci) {path.push_back(parenti);parenti pPath[parenti];}path.push_back(srci);//需要反转一下因为我们从s-x-v//是从v的父亲为x再推出x的父亲为s才结束的reverse(path.begin(), path.end());for (auto index : path) {cout _vertexs[index] -;}cout 权值和 dist[i] endl;}}}Dijkstra算法存在的问题是不支持图中带负权路径如果带有负权路径则可能会找不到一些路 径的最短路径。
二、FloydWarshall弗洛伊德
多源最短路径Floyd-Warshall算法是解决任意两点间的最短路径的一种算法。
1.方法
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 2…k-1}取得的一条最短路径。
核心将中间经过的k当成所经过s-…-j中间经过的所有中间顶点集合中的一个把中间的所有顶点看成k。 2.代码实现
void FloydWarshall(vectorvectorW vvDist, vectorvectorint vvpPath){size_t n _vertexs.size();vvDist.resize(n);vvpPath.resize(n);// 初始化权值和路径矩阵for (size_t i 0; i n; i){vvDist[i].resize(n, MAX_W);vvpPath[i].resize(n, -1);}//vvpPath[i][j]表示i-j,j的父亲为i// 直接相连的边更新一下//把目前已知直接相连的边放入vvDist中并更新vvpPath[i][j]for (size_t i 0; i n; i){for (size_t j 0; j n; j){if (_matrix[i][j] ! MAX_W){vvDist[i][j] _matrix[i][j];vvpPath[i][j] i;}if (i j){vvDist[i][j] W();}}}// 最短路径的更新i- {其他顶点} -j//这里要进行k次的原因是因为我们所有结点都有可能//成为src与dst的中间结点所以要考虑所有情况for (size_t k 0; k n; k){for (size_t i 0; i n; i){for (size_t j 0; j n; j){// k 作为的中间点尝试去更新i-j的路径if (vvDist[i][k] ! MAX_W vvDist[k][j] ! MAX_W vvDist[i][k] vvDist[k][j] vvDist[i][j]){vvDist[i][j] vvDist[i][k] vvDist[k][j];vvpPath[i][j] vvpPath[k][j];//因为这里k实际上是中间顶点集合// 找跟j相连的上一个邻接顶点// 如果k-j 直接相连上一个点就kvvpPath[k][j]存就是k// 如果k-j 没有直接相连k-...-x-jvvpPath[k][j]存就是x}}}// 打印权值和路径矩阵观察数据for (size_t i 0; i n; i){for (size_t j 0; j n; j){if (vvDist[i][j] MAX_W){//cout * ;printf(%3c, *);}else{//cout vvDist[i][j] ;printf(%3d, vvDist[i][j]);}}cout endl;}cout endl;for (size_t i 0; i n; i){for (size_t j 0; j n; j){//cout vvParentPath[i][j] ;printf(%3d, vvpPath[i][j]);}cout endl;}cout endl;}}};完整源码
如果对Graph这些代码不太熟悉的小伙伴可以参考我之前写的【数据结构】图的创建邻接矩阵邻接表以及深度广度遍历BFS,DFS
namespace matrix {//V为顶点类型W为边权值类型MAX_W为权值最大值也就是无效值//Direction用来判断是不是有向图false为无向图templateclass V,class W,W MAX_WINT_MAX,bool Directionfalseclass Graph {public:Graph() default;Graph(const V* a, size_t n) {_vertexs.reserve(n);for (size_t i 0; i n; i) {_vertexs.push_back(a[i]);_indexMap[a[i]] i;//将顶点存入_vertexs下标映射存进map}_matrix.resize(n);for (size_t i 0; i _matrix.size(); i) {_matrix[i].resize(n, MAX_W);//邻接矩阵默认初始值为无效值}}size_t GetVertexIndex(const V v) {//获得对应顶点在数组中的下标auto it _indexMap.find(v);if (it ! _indexMap.end()) {return it-second;//有这个顶点返回其下标}else {throw(顶点不存在);return -1;}}void _AddEdge(size_t srci, size_t dsti, const W w) {//存入权值_matrix[srci][dsti] w;if (Direction false) {_matrix[dsti][srci] w;//无向图要两个方向都存}}void AddEdge(const V src, const V dst, const W w) {//添加边与顶点的关系。从src到dst方向的关系size_t srci GetVertexIndex(src);size_t dsti GetVertexIndex(dst);//先获取其对应的下标_AddEdge(srci, dsti, w);}void Print() {for (size_t i 0; i _vertexs.size(); i) {cout [ i ] - _vertexs[i] endl;}//打印顶点集cout endl;//打印邻接矩阵for (size_t i 0; i _matrix.size(); i) {cout i ;for (size_t j 0; j _matrix[i].size(); j) {if (_matrix[i][j] MAX_W) {printf(%4c, *);}else {printf(%4d, _matrix[i][j]);}}cout endl;}}void BFS(const V src) {size_t srci GetVertexIndex(src);queueintq;q.push(srci);vectorboolvisited(_vertexs.size(), false);visited[srci] true;//标记这个顶点被访问过了int levelSize 1;while (!q.empty()) {//levelSize为当前层的大小for (size_t i 0; i levelSize; i) {int front q.front();q.pop();cout front : _vertexs[front] ;for (size_t i 0; i _vertexs.size(); i) {if (_matrix[front][i] ! MAX_W visited[i] false) {q.push(i);visited[i] true;//标记这个顶点被访问过了}}}levelSize q.size();//更新当前层的数量cout endl;}cout endl;}void _DFS(size_t srci, vectorbool visited) {cout srci : _vertexs[srci] endl;visited[srci] true;//标记这个顶点被访问过了for (size_t i 0; i _vertexs.size(); i) {if (_matrix[srci][i] ! MAX_W visited[i] false) {_DFS(i, visited);}}}void DFS(const V src) {size_t srci GetVertexIndex(src);vectorboolvisited(_vertexs.size(), false);_DFS(srci, visited);}typedef GraphV, W, MAX_W, false Self;//建立边的类保存边的两个顶点下标和权值struct Edge {size_t _srci;size_t _dsti;W _w;Edge(size_t srci,size_t dsti,W w):_srci(srci),_dsti(dsti),_w(w){}bool operator(const Edge e)const {return _w e._w;//小根堆判断}};W Kruskal(Self minTree){//minTree为最小生成树刚开始什么都没有size_t n _vertexs.size();//初始化最小生成树minTree._vertexs _vertexs;minTree._indexMap _indexMap;minTree._matrix.resize(n);for (size_t i 0; i n; i){minTree._matrix[i].resize(n, MAX_W);}//我们每次选边从全部边中选出最小的保证不构成回路的情况//所以我们可以考虑用小根堆来存入边这样每次方便找最小的priority_queueEdge, vectorEdge, greaterEdge minque;for (size_t i 0; i n; i){for (size_t j 0; j n; j){if (i j _matrix[i][j] ! MAX_W){//将所有有效值边放进堆中minque.push(Edge(i, j, _matrix[i][j]));}}}int size 0;W totalW W();UnionFindSet ufs(n); // 选出n-1条边while (!minque.empty()){//取出最小边Edge min minque.top();minque.pop();if (!ufs.InSet(min._srci, min._dsti))//判断是否成环{//cout _vertexs[min._srci] - _vertexs[min._dsti] :min._w endl;//不成环就将当前边放入最小生成树当中minTree._AddEdge(min._srci, min._dsti, min._w);//并把这两个顶点放入同一个并查集集合当中ufs.Union(min._srci, min._dsti);size;totalW min._w;//权值总和增加}else{//cout 构成环;//cout _vertexs[min._srci] - _vertexs[min._dsti] : min._w endl;}}if (size n - 1)//边数选够说明最小生成树//创建成功{return totalW;}else{return W();}}W Prim(Self minTree, const W src){size_t srci GetVertexIndex(src);size_t n _vertexs.size();minTree._vertexs _vertexs;minTree._indexMap _indexMap;minTree._matrix.resize(n);for (size_t i 0; i n; i){minTree._matrix[i].resize(n, MAX_W);}vectorbool X(n, false);vectorbool Y(n, true);X[srci] true;Y[srci] false;// 从X-Y集合中连接的边里面选出最小的边priority_queueEdge, vectorEdge, greaterEdge minq;// 先把srci连接的边添加到小根堆中for (size_t i 0; i n; i){if (_matrix[srci][i] ! MAX_W){minq.push(Edge(srci, i, _matrix[srci][i]));}}cout Prim开始选边 endl;size_t size 0;//选出边的数量W totalW W();//权值之和while (!minq.empty()){Edge min minq.top();minq.pop();// 最小边的目标点也在X集合则构成环if (X[min._dsti]){//cout 构成环:;//cout _vertexs[min._srci] - _vertexs[min._dsti] : min._w endl;}else{//从Y中选出顶点minTree._AddEdge(min._srci, min._dsti, min._w);//加入最小生成树//cout _vertexs[min._srci] - _vertexs[min._dsti] : min._w endl;X[min._dsti] true;Y[min._dsti] false;size;totalW min._w;if (size n - 1)break;//把新加入顶点相关的边都放入小根堆中for (size_t i 0; i n; i){if (_matrix[min._dsti][i] ! MAX_W Y[i]){minq.push(Edge(min._dsti, i, _matrix[min._dsti][i]));}}}}if (size n - 1){return totalW;}else{return W();}}void PrintShortPath(const V src, const vectorW dist, const vectorint pPath) {size_t srci GetVertexIndex(src);size_t n _vertexs.size();for (size_t i 0; i n; i) {if (i ! srci) {vectorintpath;//path为src到其他顶点路径size_t parenti i;while (parenti ! srci) {path.push_back(parenti);parenti pPath[parenti];}path.push_back(srci);//需要反转一下因为我们从s-x-v//是从v的父亲为x再推出x的父亲为s才结束的reverse(path.begin(), path.end());for (auto index : path) {cout _vertexs[index] -;}cout 权值和 dist[i] endl;}}}void Dijkstra(const V src, vectorW dist, vectorint pPath){//dist存的src到其他点的最短路径// vectorint pPath 记录srci-其他顶点最短路径父顶点数组size_t srci GetVertexIndex(src);size_t n _vertexs.size();dist.resize(n, MAX_W);pPath.resize(n, -1);dist[srci] 0;//自己到自己距离为0pPath[srci] srci;// 已经确定最短路径的顶点集合vectorbool S(n, false);for (size_t j 0; j n; j){int u srci;//u为当前最短路径顶点W min MAX_W;//min为起始点到u的距离for (size_t i 0; i n; i){if (S[i] false dist[i] min){u i;min dist[i];}}//找到与当前起始点直接相连的最短路径的顶点后//将其位置置为true表明已经选入S[u] true;// 松弛算法更新一遍u连接的所有边看是否能更新出更短连接路径for (size_t v 0; v n; v){// 如果srci-u u-k 比 srci-k更短 则进行更新if (S[v] false _matrix[u][v] ! MAX_W dist[u] _matrix[u][v] dist[v]){dist[v] dist[u] _matrix[u][v];pPath[v] u;}}}}void FloydWarshall(vectorvectorW vvDist, vectorvectorint vvpPath){size_t n _vertexs.size();vvDist.resize(n);vvpPath.resize(n);// 初始化权值和路径矩阵for (size_t i 0; i n; i){vvDist[i].resize(n, MAX_W);vvpPath[i].resize(n, -1);}//vvpPath[i][j]表示i-j,j的父亲为i// 直接相连的边更新一下//把目前已知直接相连的边放入vvDist中并更新vvpPath[i][j]for (size_t i 0; i n; i){for (size_t j 0; j n; j){if (_matrix[i][j] ! MAX_W){vvDist[i][j] _matrix[i][j];vvpPath[i][j] i;}if (i j){vvDist[i][j] W();}}}// 最短路径的更新i- {其他顶点} -j//这里要进行k次的原因是因为我们所有结点都有可能//成为src与dst的中间结点所以要考虑所有情况for (size_t k 0; k n; k){for (size_t i 0; i n; i){for (size_t j 0; j n; j){// k 作为的中间点尝试去更新i-j的路径if (vvDist[i][k] ! MAX_W vvDist[k][j] ! MAX_W vvDist[i][k] vvDist[k][j] vvDist[i][j]){vvDist[i][j] vvDist[i][k] vvDist[k][j];vvpPath[i][j] vvpPath[k][j];//因为这里k实际上是中间顶点集合// 找跟j相连的上一个邻接顶点// 如果k-j 直接相连上一个点就kvvpPath[k][j]存就是k// 如果k-j 没有直接相连k-...-x-jvvpPath[k][j]存就是x}}}// 打印权值和路径矩阵观察数据for (size_t i 0; i n; i){for (size_t j 0; j n; j){if (vvDist[i][j] MAX_W){//cout * ;printf(%3c, *);}else{//cout vvDist[i][j] ;printf(%3d, vvDist[i][j]);}}cout endl;}cout endl;for (size_t i 0; i n; i){for (size_t j 0; j n; j){//cout vvParentPath[i][j] ;printf(%3d, vvpPath[i][j]);}cout endl;}cout endl;}}private:vectorV_vertexs;//顶点集合mapV, int_indexMap;//存顶点与数组下标的映射关系vectorvectorW_matrix;//邻接矩阵};}
