[高阶数据结构六]最短路径算法
1.前言
最短路径算法是在图论的基础上讲解的，如果你还不知道图论的相关知识的话，可以阅读下面几篇文章。
[高阶数据结构四] 初始图论_初始图结构-CSDN博客
[高阶数据结构五] 图的遍历和最小生成树_图的遍历和生成树求解-CSDN博客
本章重点：
本章主要讲解图论的三种算法---Dijkstra，Ballman-Ford，Floyd-Warshall算法。
2.单源最短路径
所谓的单源最短路径,也就是从图中任意一点出发, 到图中每个节点的最短路径,也就是最小的权值和。
举个例子：
为了要统计源点Srci即s到yztx四点的最短路径，通常使用两个数组来解决。
其中一个表示的是，从源点到当前点的最短路径的权值
另外一个表示的是，从源点到当前点最短路径的路径是什么。
//存储任意点到图中其他点的最短路径的权值
vector<W>& dist
//记录srci->其他顶点最短路径父顶点数组
vector<int>& parentPath
这么说可能有点抽象，看如下图。
数组下标x处，对应的是t所在位置的下标，而t处对应的下标所在的位置是y。
dist中dist[4]表示从源点到x的最短路径为9。
3.Dijkstra算法
针对一个带权有向图 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 的代价之和，否则维持原样。
这样说有点抽象--但是如果你阅读了前面两篇文章，你会发现这个算法和Prim算法是有点类似的。
举例如下：
a处唯一确定的节点就是s,其余均是不确定的。在这里面找出一个与A直接相连，且路径是最短的出来，然后这个值那么一定是可以唯一确定的。
b处也用a处的方法，然后可以确定的节点是s,y，其余均为不确定的。
依次重复，有几个结点那么重复几次，一定可以把所有的节点确定下来。（这里的前提是权值均为正，不可以有负的）。后续解释为什么。
代码如下：
void Dijkstra(const V& src, vector<W>& dist, vector<int>& parentPath)
{
//dist[i]表示srci到i位置的最短路径的权值
//parentPath[i]表示推导出当前节点的下标.
//即srci->B位置的最小权值是由srci->A->B推导而来,所以存储的是A的下标
size_t n = _ver.size();
dist.resize(n, int_MAX);
parentPath.resize(n, -1);//-1表示初始时，没有路径能走到
int srci = GetIndex(src);
dist[srci] = 0;
dist[srci] = W();
parentPath[srci] = srci;
vector<bool> visited(n, false);
//n个节点,一共会更新n次,也可以判断visited数组中的元素是否全为true
for (int s = 0; s < n; s++)
{
//每次找出dist中没有遍历过的，当前的最小的权值来做确定的顶点及边
int u = 0;//表示顶点
int min = int_MAX;//表示srci->u的权值
for (int i = 0; i < n; i++)
{
if (visited[i] == false && dist[i] < min)
{
u = i;
min = dist[i];
}
}
//到这里就找到了最小的
visited[u] = true;
//开始进行松弛操作，即从srci->u->v的权值是否比srci->v的权值小，小的话就在dist中换掉
for (int v = 0; v < n; v++)
{
//这里松弛操作还有一个关键点，就是已经选定了的，即在visited里面是true的，后续哪怕找到了
//比当前小的路径，也不在进行松弛操作了。理论上是不可能的，含有负权值除外
if (visited[v]==false
&&_martix[u][v] != int_MAX
&& dist[v] > dist[u] + _martix[u][v])
{
dist[v] = dist[u] + _martix[u][v];
parentPath[v] = u;//表示u这个顶点->v顶点
}
}
}
}这个算法是不支持有负权值的，这是因为一旦有了负权值，你之前唯一确定的点，可能就不是最短路径的值了。因为这里出现了环，那么可能出现的问题是:一直在环里面兜圈子，那么就会出现无穷小的情况。
例如：
4.BellMan-Ford算法
这个算法能够解决带有负权值的问题。
他是通过暴力的解法来搞定这个问题的。 它的时间复杂度是O(N^3). 它的思路就是以所有顶点为起始点,更新所有相连的边。
代码如下：
bool BellmanFord(const V& src, vector<W>& dist,vector<int>& parentPath)
{
size_t n = _ver.size();
dist.resize(n, int_MAX);
parentPath.resize(n, -1);//-1表示暂时所有的都没有通路
int srci = GetIndex(src);
dist[srci] = W();
for (int k = 0; k < n-1; k++)
{
//加这个条件是有时候可能走3轮就不会再走后面的循环了，为了节省时间
bool exchange = false;
//开始暴力遍历n-1条边，并且更新权值
cout << "第[" << k << "轮]" << endl;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
//srci ->i + i-> j 与srci->j的比较
if (_martix[i][j] != int_MAX && dist[i] + _martix[i][j] < dist[j])
{
cout << "[" << _ver[i] << "]" << "->" << _ver[j] << ":" \
<< _martix[i][j] << endl;
dist[j] = dist[i] + _martix[i][j];
parentPath[j] = i;
exchange = true;
}
}
}
//到这里第一遍n-1条边的权值已经更新完了，但是有可能导致的因数是前面确定的边的值可能不是最小值，
//前面确定边的值必须由后面确定边的值推导而来。一次暴力遍历n-1条边，可以至少确定一个顶点，有n个
//顶点，所以至少要遍历n-1遍
if (exchange == false) break;
}
//这里判断负权值的回路是否构成了环
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
//srci ->i + i-> j 与srci->j的比较
if (_martix[i][j] != int_MAX && dist[i] + _martix[i][j] < dist[j])
{
return false;
}
}
}
return true;
}5.多源最短路径问题
简单的来说多源最短路径问题就是任意两点间的最短路径的权值以及走过的节点是什么。
那么这就需要两个二维数组来表示上述两个情况了。
一个二维数组存储顶点i->j的最短路径的权值和, 另外一个数组存储 (i,j)的父节点下标. i,j是最短路径的节点。
6.Folyd-WarShall算法
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}取得的一条最短路径
举个例子：
代码如下：
void FloydWarShall(vector<vector<W>>& vvDist, vector<vector<int>>& vvParentPath)
{
//任意两点的最短路径
//1.初始化
size_t n = _ver.size();
vvDist.resize(n);
vvParentPath.resize(n);
for (int i = 0; i < n; i++)
{
vvDist[i].resize(n, int_MAX);
vvParentPath[i].resize(n, -1);
}
//先初始化那些直接相连的
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (i == j)
{
vvDist[i][j] = 0;
vvParentPath[i][j] = -1;
}
if (_martix[i][j] != int_MAX)
{
vvDist[i][j] = _martix[i][j];
vvParentPath[i][j] = i;
}
}
}
//任意两点间的最短路径---abcdef 求a->f之间的最短路径，假设中间点为k,
//可能经过k点，也可能不经过k点
//若经过k点，dist[i][j]=dist[i][k]+dist[k][j]
//不经过k点的话，那么dist[i][j]=dist[i][j],此时i-j之间是少了k点这个值的
//那么问题就转换成找k点了，那么k点是谁呢？ a->f k点可能是b c d e
//若求的是b->e最短路径呢？ 那么k点可能是a c e f。
//通过上述分析发现，任意一个点都有可能成为k点。
for (int k = 0; k < n; k++)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (vvDist[i][k] != int_MAX && vvDist[k][j] != int_MAX
&& vvDist[i][k] + vvDist[k][j] < vvDist[i][j])
{
vvDist[i][j] = vvDist[i][k] + vvDist[k][j];
vvParentPath[i][j] = vvParentPath[k][j];
//这里为什么不直接是k呢？
//首先如果k是推出j的上一个顶点，那么vvp[k][j]一定放的是k
//那么如果k不是推出j的上一个顶点呢？那么就不能填k，
//但是上一个顶点一定存放在vvp[k][j]里面
}
}
}
}7.总结
这些算法都比较抽象，博主花了很大很大的功夫才理解他们，如果真要完全手撕，那么我想博主起码最少需要几个小时，因此就算不会手撕也没有关系，只需要知道思路即可。在面试中，能讲出思路也是一个加分项呢。