【数据结构】最短路径算法实现（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。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
hdu2544（单源最短路径）

hdu2544（单源最短路径）

模板题： //题意：求1到n的最短路径，模板题#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#i
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯，先赞后看哦~🎈🎈 🏆 作者简介：景天科技苑 🏆《头衔》：大厂架构师，华为云开发者社区专家博主，阿里云开发者社区专家博主，CSDN全栈领域优质创作者，掘金优秀博主，51CTO博客专家等。 🏆《博客》：Python全栈，前后端开发，小程序开发，人工智能，js逆向，App逆向，网络系统安全，数据分析，Django，fastapi
阅读更多...
让树莓派智能语音助手实现定时提醒功能

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现，因为rasa本身是带有remindschedule模块的。不过经过一番折腾后，忽然发现，chatbot上实现的定时，语音助手不一定会有响应。因为，我目前语音助手的代码设置了长时间无应答会结束对话，这样一来，chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢？ 我最后选择的方法是用threading.Time
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2