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

---

前言

最短路径问题：从在带权有向图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;//邻接矩阵};}