最短路径问题：从在带权有向图G中的某一顶点出发，找出一条通往另一顶点的最短路径，最短也就是沿路径各边的权值总和达到最小。
最短路径分为图中单源路径和多源路径。
本文会介绍Dijkstra和Bellman-Ford解决单源路径的问题
Floyd-Warshall解决多路径的问题
单源最短路径--Dijkstra算法
单源问题，对于图中给定的结点u，求出到达各个结点v的路径代价和最小。最小路径可能是直接u->v
也可能是从u->t->v 。
Dijkstra算法就是解决所有边非负权值的最短路径。一般是从给出点u到终点v.
算法的思路
将图中的所有结点可以分为S和Q，S是已经确定最短路径的集合，Q是还没被访问的集合)(初始化时，将s放到集合中)
每一次从Q中选出一个s到Q代价最小的点u，把u从s移出放到S中，对u的相邻v 进行松弛更新。
松弛更新：判断s->u(已经确定了) u->v的路径是否小于s->v（已经确定的）
如果是的话，就更新s->v
直到更新所有的Q结点
在我们的模拟实现中
保存一张dist[]数组，用来表示s到某点的最短路径
S[]数组用来表示已经确定最短路径的顶点、
pPath用来存储路径前一个顶点的下标
通过画图梳理这个过程
首次初始化时，dist数组s位置是0，其它为无穷，pPath数组s位置是缺省值
第二轮：寻找最短路径s-s 松弛更新出s->t s->y
第三步 选出最小v s->y(s->s已经被标记过)
松弛更新出s-y-t s-y-x s-y-z
第三轮选边 选出s->z 对z相邻的边松弛更新
s->z->x(13)
s->z->s（14 不更新）
第四轮
选边s->t
第五轮 选出s->x 松弛更新出 x->z(不更新，已经是最短路径)
松弛更新不适合用于带负权值的路径
因为无法确定第一轮的最小值
void Dijkstra(const V& src, vector<W>& dist, vector<int>& pPath)
{
size_t srci = GetVertexIndex(src);
size_t n = _vertexs.size();
dist.resize(n, MAX_W);
pPath.resize(n, -1);
//自身就是0
dist[srci] = W();
pPath[srci] = srci;
//标记容器
vector<bool> S(n, false);
for (size_t j = 0; j < n; j++)
{
int u = 0;
W min = MAX_W;
for (size_t i = 0; i < n; i++)
{
if (S[i] == false && dist[i] < min)
{
u = i;
min = dist[i];
}
}
S[u] = true;
//松弛更新
for (size_t v = 0; v < n; v++)
{
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;
}
}
}
}
单源最短路径--Bellman-Ford算法
迪杰斯特拉算法不能解决带负权值边的最短路径，贝尔曼福特就采用暴力的方式解决了带负权值边的路径问题，还能判断出回路是否带有负权值。
贝尔曼福特算法的思路是将 srci-> j的路径问题划分为srci-> i i->j的路径最短问题
对于从源顶点 s 到目标顶点 j 的路径来说，如果存在从源顶点 s 到顶点 i 的路径，还存在一条从顶点 i 到顶点 j 的边，并且其权值之和小于当前从源顶点 s 到目标顶点 j 的路径长度，则可以对顶点 j j 的估计值和前驱顶点进行松弛更新。
是利用已经确定的最短路径srci -i 再加上i->j的边权来更新的最短路径。
确定完所有的顶点后，都必须重新进行更新，因为每一条路径的确定，都有可能影响前一轮的路径更新。故需要遍历K次。K为N次。(因为所有的点都在变，都需要更新。)
初始化时，dist[srci]初始化为缺省值
第一次i==0时，更新出t y
第二次,i==1更新出x z
i==2时，更新出 x s(不更新，目前是最短路径)
i==3时，更新出t->z
i==4时，用x更新出t
结束第一轮
此时还需要进行下一轮的更新
下一轮再i==3时，更新出t->z=-4
bool BellmanFord(const V& src, vector<W>& dist, vector<int>& pPath)
{
size_t n = _vertexs.size();
size_t srci = GetVertexIndex(src);
dist.resize(n, MAX_W);
pPath.resize(n, -1);
dist[srci] = W();
//最多更新k轮
for (size_t k = 0; k < n; k++)
{
bool updata = false;
cout << "更新第:" << k << "轮" << endl;
//srci->i+i->j
for (size_t i = 0; i < n; i++)
{
for (size_t j = 0; j < n; j++)
{
if (_matrix[i][j] != MAX_W && dist[i] + _matrix[i][j] < dist[j])
{
updata = true;
cout << _vertexs[i] << "->" << _vertexs[j] << ":" << _matrix[i][j] << endl;
dist[j] = dist[i] + _matrix[i][j];
pPath[j] = i;
}
}
}
if (!updata)
break;
}
//如果还能更新，就是带负路径
for (size_t i = 0; i < n; i++)
{
for (size_t j = 0; j < n; j++)
{
if (_matrix[i][j] != MAX_W && dist[i] + _matrix[i][j] < dist[j])
{
return false;
}
}
}
return true;
}
利用程序编写过程和我们的画图一致
贝尔曼福特算法是暴力求解，有相当高的时间复杂度O(N^3)，但是能够解决负权值问题。
多源最短路径--Floyd-Warshall算法
Floyd-Warshall算法是解决任意两点间的最短路径的一种算法。
弗洛伊德算法考虑的是中间最短路径的中间结点，设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}取得的一条最短路径。
Floyd-Warshall算法是一种动态规划算法，其运行时间为o(n^3)与最短路径路径上通常的假设一样，假设权重可以为负，但不能有权重为负的环路。
如果存在从顶点 i 到顶点 k 的路径，还存在从顶点 k 到顶点 j 的路径，并且这两条路径的权值之和小于当前从顶点 i 到顶点 j 的路径长度，则可以对顶点 j 的估计值和前驱顶点进行松弛更新。
算法原理：
费洛伊徳算法就是将最短路径分成dist[i][k]+ dist[k][j]与dist[k][j]的问题
算法需要一个二维的vvdist记录最短路径，vvpPath标记父路径
将直接相连的视作最短路径
进行k次更新（K为n，i和j都在变换）
动态规划更新vvdist
注意vvpPath[i][j]的前一个不再是i而应该是递归的vvpPath[k][j]，可能变化一次，也可能变化好多次
void FloydWarshall(vector<vector<W>>& vvDist, vector<vector<int>>& vvpPath)
{
size_t n = _vertexs.size();
vvDist.resize(n, vector<W>(n, MAX_W));
vvpPath.resize(n, vector<int>(n, -1));
//更新权值和父路径
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();
}
}
}
//O(N^3)
//最多更新k次
for (size_t k = 0; k < n; k++)
{
for (size_t i = 0; i < n; i++)
{
for (size_t j = 0; j < n; j++)
{
//存在 i->k k->j 且<dist[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];
}
}
}
// 打印权值和路径矩阵观察数据
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;
}
}最短路径的总结
迪杰斯特拉算法是基于贪心算法设计，解决非负数权值的路径问题。将顶点分为S和Q，每次都从Q中选出最小的权值u放到s中，然后将u的相邻边进行松弛调整。
贝尔曼福特算法是暴力求解，能求解出带负权值的路径，能判断负权环路。是一个时间复杂度为o(N^3)的算法。要进行K次松弛调整。每一次都是通过dist[i]+_matrix[i][j]更新权值
费洛伊徳算法是动态规划的思想，将路径分为i->k k->j的思想。同样要进行K轮次的更新。复杂度为0(N^3)。能够求解任意俩顶点的最短路径。
