【数据结构】最短路径算法实现（Dijkstra（迪克斯特拉），FloydWarshall（弗洛伊德） ）

2023-12-24 04:52
文章标签 算法 实现 路径 数据结构 最短 dijkstra 斯特拉 弗洛伊德 floydwarshall 迪克

本文主要是介绍【数据结构】最短路径算法实现（Dijkstra（迪克斯特拉），FloydWarshall（弗洛伊德） ），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

  • 前言
  • 一、Dijkstra（迪克斯特拉）
    • 1.方法：
    • 2.代码实现
  • 二、FloydWarshall（弗洛伊德）
    • 1.方法
    • 2.代码实现
  • 完整源码

前言

最短路径问题：从在带权有向图G中的某一顶点出发，找出一条通往另一顶点的最短路径，最短也就是沿路径各边的权值总和达到最小。
单源最短路径问题：给定一个图G = ( V ， E ) G=(V，E)G=(V，E)，求源结点s ∈ V s∈Vs∈V到图
中每个结点v ∈ V v∈Vv∈V的最短路径

一、Dijkstra（迪克斯特拉）

1.方法：

针对一个带权有向图G，将所有结点分为两组S和Q，S是已经确定最短路径的结点集合，在初始时
为空（初始时就可以将源节点s放入，毕竟源节点到自己的代价是0），Q 为其余未确定最短路径
的结点集合，每次从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直接相连的为t，y。最小的边为5，即y顶点，其为s到y的最短距离，然后以y为起点，与y直接相连的有t，x，z。最小的边为2即z点，y到z最短为2，所以s到z最短为7，以此类推，直到所有点都被当过起点后结束）
在这里插入图片描述

2.代码实现

void Dijkstra(const V& src, vector<W>& dist, vector<int>& pPath){//dist存的src到其他点的最短路径// vector<int> 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;// 已经确定最短路径的顶点集合vector<bool> 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 vector<W>& dist, const vector<int>& pPath) {size_t srci = GetVertexIndex(src);size_t n = _vertexs.size();for (size_t i = 0; i < n; i++) {if (i != srci) {vector<int>path;//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的两段最短路径p1，p2。p1
是从i到k且中间节点属于{1，2，…，k-1}取得的一条最短路径。p2是从k到j且中间节点属于{1，
2，…，k-1}取得的一条最短路径。

核心将中间经过的k当成所经过s->…->j中间经过的所有中间顶点集合中的一个，把中间的所有顶点看成k。

在这里插入图片描述

在这里插入图片描述

2.代码实现

void FloydWarshall(vector<vector<W>>& vvDist, vector<vector<int>>& 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 直接相连，上一个点就k，vvpPath[k][j]存就是k// 如果k->j 没有直接相连，k->...->x->j，vvpPath[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为无向图template<class V,class W,W  MAX_W=INT_MAX,bool Direction=false>class 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);queue<int>q;q.push(srci);vector<bool>visited(_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, vector<bool>& 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);vector<bool>visited(_vertexs.size(), false);_DFS(srci, visited);}typedef Graph<V, 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_queue<Edge, vector<Edge>, greater<Edge>> 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);}vector<bool> X(n, false);vector<bool> Y(n, true);X[srci] = true;Y[srci] = false;// 从X->Y集合中连接的边里面选出最小的边priority_queue<Edge, vector<Edge>, greater<Edge>> 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 vector<W>& dist, const vector<int>& pPath) {size_t srci = GetVertexIndex(src);size_t n = _vertexs.size();for (size_t i = 0; i < n; i++) {if (i != srci) {vector<int>path;//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, vector<W>& dist, vector<int>& pPath){//dist存的src到其他点的最短路径// vector<int> 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;// 已经确定最短路径的顶点集合vector<bool> 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(vector<vector<W>>& vvDist, vector<vector<int>>& 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 直接相连，上一个点就k，vvpPath[k][j]存就是k// 如果k->j 没有直接相连，k->...->x->j，vvpPath[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:vector<V>_vertexs;//顶点集合map<V, int>_indexMap;//存顶点与数组下标的映射关系vector<vector<W>>_matrix;//邻接矩阵};}

这篇关于【数据结构】最短路径算法实现（Dijkstra（迪克斯特拉），FloydWarshall（弗洛伊德） ）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/530595。

相关文章

如何使用C#串口通讯实现数据的发送和接收

如何使用C#串口通讯实现数据的发送和接收

《如何使用C#串口通讯实现数据的发送和接收》本文详细介绍了如何使用C#实现基于串口通讯的数据发送和接收,通过SerialPort类,我们可以轻松实现串口通讯,并结合事件机制实现数据的传递和处理,感兴趣... 目录1. 概述2. 关键技术点2.1 SerialPort类2.2 异步接收数据2.3 数据解析2.
阅读更多...
mybatis-plus 实现查询表名动态修改的示例代码

mybatis-plus 实现查询表名动态修改的示例代码

《mybatis-plus实现查询表名动态修改的示例代码》通过MyBatis-Plus实现表名的动态替换,根据配置或入参选择不同的表,本文主要介绍了mybatis-plus实现查询表名动态修改的示... 目录实现数据库初始化依赖包配置读取类设置 myBATis-plus 插件测试通过 mybatis-plu
阅读更多...
Qt把文件夹从A移动到B的实现示例

Qt把文件夹从A移动到B的实现示例

《Qt把文件夹从A移动到B的实现示例》本文主要介绍了Qt把文件夹从A移动到B的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学... 目录如何移动一个文件？ 如何移动文件夹（包含里面的全部内容）：如何删除文件夹：QT 文件复制，移动(
阅读更多...
Flask 验证码自动生成的实现示例

Flask 验证码自动生成的实现示例

《Flask验证码自动生成的实现示例》本文主要介绍了Flask验证码自动生成的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习... 目录生成图片以及结果处理验证码蓝图html页面展示想必验证码大家都有所了解，但是可以自己定义图片验证码
阅读更多...
VSCode配置Anaconda Python环境的实现

VSCode配置Anaconda Python环境的实现

《VSCode配置AnacondaPython环境的实现》VisualStudioCode中可以使用Anaconda环境进行Python开发,本文主要介绍了VSCode配置AnacondaPytho... 目录前言一、安装 Visual Studio Code 和 Anaconda二、创建或激活 conda
阅读更多...
使用mvn deploy命令上传jar包的实现

使用mvn deploy命令上传jar包的实现

《使用mvndeploy命令上传jar包的实现》本文介绍了使用mvndeploy:deploy-file命令将本地仓库中的JAR包重新发布到Maven私服,文中通过示例代码介绍的非常详细,对大家的学... 目录一、背景二、环境三、配置nexus上传账号四、执行deploy命令上传包1. 首先需要把本地仓中要
阅读更多...
JAVA封装多线程实现的方式及原理

JAVA封装多线程实现的方式及原理

《JAVA封装多线程实现的方式及原理》：本文主要介绍Java中封装多线程的原理和常见方式,通过封装可以简化多线程的使用,提高安全性,并增强代码的可维护性和可扩展性,需要的朋友可以参考下... 目录前言一、封装的目标二、常见的封装方式及原理总结前言在 Java 中，封装多线程的原理主要围绕着将多线程相关的操
阅读更多...
MySQL中实现多表查询的操作方法(配sql+实操图+案例巩固 通俗易懂版)

MySQL中实现多表查询的操作方法(配sql+实操图+案例巩固 通俗易懂版)

《MySQL中实现多表查询的操作方法(配sql+实操图+案例巩固通俗易懂版)》本文主要讲解了MySQL中的多表查询,包括子查询、笛卡尔积、自连接、多表查询的实现方法以及多列子查询等,通过实际例子和操... 目录复合查询1. 回顾查询基本操作group by 分组having1. 显示部门号为10的部门名，员
阅读更多...
Windows系统下如何查找JDK的安装路径

Windows系统下如何查找JDK的安装路径

《Windows系统下如何查找JDK的安装路径》：本文主要介绍Windows系统下如何查找JDK的安装路径,文中介绍了三种方法,分别是通过命令行检查、使用verbose选项查找jre目录、以及查看... 目录一、确认是否安装了JDK二、查找路径三、另外一种方式如果很久之前安装了JDK，或者在别人的电脑上，想
阅读更多...
java导出pdf文件的详细实现方法

java导出pdf文件的详细实现方法

《java导出pdf文件的详细实现方法》：本文主要介绍java导出pdf文件的详细实现方法,包括制作模板、获取中文字体文件、实现后端服务以及前端发起请求并生成下载链接,需要的朋友可以参考下... 目录使用注意点包含内容1、制作pdf模板2、获取pdf导出中文需要的文件3、实现4、前端发起请求并生成下载链接使
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2