一、最小生成树（无向图）
在了解最小生成树算法之前，我们首先要先了解以下的准则：
连通图中的每一棵生成树，都是原图的一个极大无环子图，即：从其中删去任何一条边，生成树就不在连通；反之，在其中引入任何一条新边，都会形成一条回路。
因此，若连通图由n个顶点组成，则其生成树必含n个顶点和n-1条边。因此构造最小生成树的准则有三条：
1. 只能使用图中的边来构造最小生成树
2. 只能使用恰好n-1条边来连接图中的n个顶点
3. 选用的n-1条边不能构成回路（少一条就不连通，多一条就会形成回路）
构造最小生成树的方法：Kruskal算法和Prim算法。这两个算法都采用了逐步求解的贪心策略。区别就是选边的方式不同。
贪心算法：是指在问题求解时，总是做出当前看起来最好的选择。也就是说贪心算法做出的不是整体最优的的选择，而是某种意义上的局部最优解。贪心算法不是对所有的问题都能得到整体最优解。
1.1 Kruskal算法
任给一个有n个顶点的连通网络N={V,E}，
首先构造一个由这n个顶点组成、不含任何边的图G={V,NULL}，其中每个顶点自成一个连通分
量，其次不断从E中取出权值最小的一条边(若有多条任取其一)，若该边的两个顶点来自不同的连通分量，则将此边加入到G中。如此重复，直到所有顶点在同一个连通分量上为止。
核心：每次迭代时，选出一条具有最小权值，且两端点不在同一连通分量上的边（意思就是不能导致成环），加入生成树。
首先声明一下我的算法都是用的邻接矩阵去实现。 关于邻接矩阵的基本框架如下，具体是如何写出来的可以参照博主关于图论基础知识的文章。
namespace Matrix //以邻接矩阵的形式封装
{
template<class V,class W, W MAX_W = INT_MAX,bool Direction = false> //V表示顶点 W表示权重 MAX_W表示默认的权重值 Direction表示是有向图还是无向图 后面两个是非类型模版参数(缺省)
class Graph
{
public:
//图创建的方式
//1、io输入 不方便测试 再oj中较为合适
//2、图结构关系写到文件，读取文件
//3、手动去添加边，这样会更方便测试！！
Graph(const V* vertexs,size_t n) //传一个顶点相关的集合进行初始化
{
_vertexs.reserve(n);
for (size_t i = 0; i < n; ++i) //初始化顶点集合
{
_vertexs.push_back(vertexs[i]);//存到顶点集合里
_IndexMap[vertexs[i]] = i;//建立顶点和下标的映射关系，方便我们进行查找
}
//初始化邻接矩阵
_matrix.resize(n);
for (auto& e : _matrix) e.resize(n, MAX_W);
}
//获取顶点的下标(为什么要单独给这样一个函数呢？因为可能给的是一个错误的顶点，要检查一下)
size_t GetVertexIndex(const V& v)
{
//有可能顶点会给错，这样在map中就找不到 所以要先检查一下
auto it = _IndexMap.find(v);
if (it != _IndexMap.end()) return it->second;
else
{
throw invalid_argument("不存在的顶点");//抛异常(异常被捕获后可以不做处理)
//断言太暴力了，会直接终止程序，并且断言在release版本下会被屏蔽
//异常被捕获后可以不作处理，程序从捕获位置继续执行。 而断言是完全无法忽略的，程序在断言失败处立即终止。
// 因此断言通常用于调试版本，用来发现程序中的逻辑错误。 虽然异常也能起到这样的作用，但是不应该用异常代替断言：
// 1) 如果发现了逻辑错误，必须修改程序，而不可能在程序中进行处理和恢复，所以不需要向外传送，没有必要使用异常。
// 2) 使用断言的开销比异常小得多，而且断言可以从发布版中完全去除。
return -1; //还是要返回，因为编译器不会在乎运行，而是会检查你在这边有没有返回
}
}
//利用序号为两个节点添加边
void _AddEdge(size_t srci, size_t dsti, const W& w)
{
_matrix[srci][dsti] = w;
//如果是无向图
if (Direction == false) _matrix[dsti][srci] = w;
}
//对两个节点添加边，以及权重关系 src代表起点 dst代表中点 w代表权重
void AddEdge(const V& src, const V& dst, const W& w)
{
size_t srci = GetVertexIndex(src);
size_t dsti = GetVertexIndex(dst);
_AddEdge(srci, dsti, w);
}
//层序遍历 但是没有一层一层出
//void BFS(const V& src) //src表示我们的起点
//{
// size_t srci = GetVertexIndex(src);//找到起点的下标
// queue<int> q;//存储下标的队列
// size_t n = _vertexs.size();//表示有多少个节点
// vector<bool> check(n);
// q.push(srci);
// check[srci] = true;//入队列就标记
// while (!q.empty())
// {
// int front = q.front();//取队头
// q.pop();
// cout << _vertexs[front] << ":"<<front<<endl;
// //然后让他的朋友进
// for (size_t i = 0; i < n; ++i)
// if (_matrix[front][i] != MAX_W && check[i] == false)
// {
// q.push(i);
// check[i] = true;
// }
// }
//}
//控制一层一层出
void BFS(const V& src) //src表示我们的起点
{
size_t srci = GetVertexIndex(src);//找到起点的下标
queue<size_t> q;//存储下标的队列
size_t n = _vertexs.size();//表示有多少个节点
vector<bool> check(n);
q.push(srci);
check[srci] = true;//入队列就标记
while (!q.empty())
{
//控制一层一层出
size_t sz = q.size();
for (size_t i = 0; i < sz; ++i) //一层出完了再去走下一层
{
size_t front = q.front();//取队头
q.pop();
cout << front<< ":" << _vertexs[front] << " ";
//然后让他的朋友进
for (size_t i = 0; i < n; ++i)
if (_matrix[front][i] != MAX_W && check[i] == false)
{
q.push(i);
check[i] = true;
}
}
cout << endl;
}
}
void _DFS(size_t srci, vector<bool>& check) //下一个位置的起点以及需要一个标记数组
{
cout << srci << ":" << _vertexs[srci] << " " << endl; //先访问 然后标记为访问过
check[srci] = true;
for (size_t i = 0; i < _vertexs.size(); ++i)
if (_matrix[srci][i] != MAX_W && check[i] == false)
_DFS(i, check);
}
void DFS(const V& src) //需要有一个起点
{
size_t srci = GetVertexIndex(src);//找到起点的下标
vector<bool> check(_vertexs.size()); //标记数组
_DFS(srci, check);
//如果是一个非连通图，可以在后面再进行一层检查check数组，然后对false的数组再进行一次访问
}
void Print()
{
//顶点
for (size_t i = 0; i <_vertexs.size() ; ++i)
cout << "[" << i << "]" << "->" << _vertexs[i] << endl; //下标映射顶点集合
cout << endl;
//打印横一行的下标
cout << " ";
for (size_t i = 0; i < _vertexs.size(); ++i) cout << i << " ";
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) cout << '*' << " ";
else cout << _matrix[i][j] << " ";
cout << endl;
}
cout << endl;
}
private:
map<V, size_t> _IndexMap; //建立顶点和下标之间的关系，方便我们根据顶点去找他的下标 比如两个顶点是否存在关系，就可以快速找到两个顶点的下标，然后去邻接矩阵看一下
vector<V> _vertexs; // 顶点集合
vector<vector<W>> _matrix; // 存储边集合的矩阵
};根据上图我们需要解决的问题如下：
1、怎么从所有边中选出权重最小的边。
2、怎么确保选中的边不会成环（关键在于如何判环）
解决方案：对于问题1，我们给该邻接矩阵封装一个和边有关的内部类。然后将所有的边存到一个优先级队列（小堆）中，将比较逻辑控制成比较权重。 这样我们每次取到的堆顶元素就是权重值最小的边，对于问题2，我们用之前学过的并查集去解决，每次拿到这个边之后，去判断该边的连个顶点是否都在并查集中，如果都在，那么就不用这条边，如果不都在，那么就将顶点加入并查集中。
注意：由于该图可能是一个非连通图，非连通图是没有生成树的，我们的检测方法就是按照上面的逻辑，在规避成环后，最后必然是取到n-1条边，所以如果我们最后没有取到n-1条边，那么该图就是非连通图，所以这个时候我们需要设置一个边计数器帮助我们在每次加入边的时候统计一下。在最后去做一个判断。
//为Kruskal算法封装一个和边有关的结构体
struct Edge
{
size_t _srci;//边的入口
size_t _dsti;//边出口
W _w; //边的权重
Edge(size_t srci, size_t dsti, const W& w)
:_srci(srci)
, _dsti(dsti)
, _w(w)
{}
bool operator>(const Edge& eg) const //控制比较逻辑
{
return _w > eg._w;
}
bool operator<(const Edge& eg) const //控制比较逻辑
{
return _w < eg._w;
}
};
//贪心算法 局部最优解
W Kruskal(Self& minTree) //Kruskal算法适合的是稀疏图，因为他的选取逻辑更多和边有关系。
{
size_t n = _vertexs.size();
//先初始化一下最小生成树
minTree._vertexs = _vertexs;
minTree._IndexMap = _IndexMap;
minTree._matrix.resize(n);
for (auto& e : minTree._matrix) e.resize(n, MAX_W); //初始化成初始状态
//将所有的边丢进优先级队列中
priority_queue<Edge, vector<Edge>, greater<Edge>> heap;//建小堆
for (size_t i = 0; i < n; ++i)
for (size_t j = 0; j < n; ++j)
if (i < j && _matrix[i][j] != MAX_W) //因为是无向图，所以只要取一半就好了
heap.push(Edge(i, j, _matrix[i][j]));
//开始选边 然后创建一个辅助我们的并查集 以及统计总权重值
UnionFindSet ufs(n);
W total = W();//用来统计我们的总权重 要用默认构造 因为不一定是int类型
size_t i = 0;//用来检测该图是否是连通图
while (i < n - 1 && !heap.empty())
{
Edge min = heap.top();
heap.pop();
//拿到最小后判断是否在一个并查集里 不在的话就将边添加进去，然后将边的顶点丢到并查集中
if (!ufs.inSet(min._srci, min._dsti))//如果两个不在一个集合里，就可以加边
{
cout << _vertexs[min._srci] << "-" << _vertexs[min._dsti] << ":" << _matrix[min._srci][min._dsti] << endl;//检测一下选的边以及他的权重
minTree._AddEdge(min._srci, min._dsti, min._w);
total += min._w;//统计权重值
//将顶点下标丢到并查集中
ufs.Union(min._srci, min._dsti);
++i;//看看最后边是否选了n-1条
}
else //为了帮助我们观察哪些边选出来之后会成环
{
cout << "成环了所以不选:";
cout << _vertexs[min._srci] << "-" << _vertexs[min._dsti] << ":" << _matrix[min._srci][min._dsti] << endl;
}
}
//但是该图可能是一个不连通的图
if (i == n - 1) return total;
else return W();//W不知道是什么类型，所以给个默认构造
}关于并查集的实现，大家可以看看博主的文章DS进阶：并查集-CSDN博客
1.2 Prim算法
W Prim(Self& minTree, const V& src) //Prim算法需要有一个起点 Prim适合稠密图 因为他的选取模式跟顶点有关系
{
size_t n = _vertexs.size();
//先初始化一下最小生成树
minTree._vertexs = _vertexs;
minTree._IndexMap = _IndexMap;
minTree._matrix.resize(n);
for (auto& e : minTree._matrix) e.resize(n, MAX_W); //初始化成初始状态
// 用一个set 或者是两个bool数组来帮助我们判环
size_t srci = GetVertexIndex(src);
set<size_t> inSet; //帮助我们存已经选过的顶点集合
inSet.insert(srci);//先将起点丢进set中
priority_queue<Edge, vector<Edge>, greater<Edge>> heap;//建小堆
for (size_t i = 0; i < n; ++i)//先将跟起点相连的所有边丢到优先级队列中(无差别入队列，但是多一层判断)
if (_matrix[srci][i] != MAX_W)
heap.push(Edge(srci, i, _matrix[srci][i]));
//开始走选边的主逻辑
W total = W();//统计总权重值
while (inSet.size() < n && !heap.empty())
{
Edge min = heap.top();
heap.pop();
//看看两个点是否同时在set中
if (inSet.find(min._dsti) == inSet.end())//必然是从srci出发的，所以我们只要保证dsti不在set中即可
{
cout << _vertexs[min._srci] << "-" << _vertexs[min._dsti] << ":" << _matrix[min._srci][min._dsti] << endl;
//都不在set中，此时将边放到最小生成树中.
minTree._AddEdge(min._srci, min._dsti, min._w);
total += min._w;
//然后将新丢进去的顶点的相连的边丢进优先级队列中
for (size_t i = 0; i < n; ++i)//先将跟起点相连的所有边丢到优先级队列中
if (_matrix[min._dsti][i] != MAX_W && inSet.find(i) == inSet.end()) //Set中有的就不要丢进去了
heap.push(Edge(min._dsti, i, _matrix[min._dsti][i]));
inSet.insert(min._dsti);
}
else
{
cout << "成环了所以不选:";
cout << _vertexs[min._srci] << "-" << _vertexs[min._dsti] << ":" << _matrix[min._srci][min._dsti] << endl;
}
}
//检测 因为该图可能是一个不连通的图，如果不连通的话就返回W的默认构造！
if (inSet.size() == n) return total;
else return W();
}1.3 小总结
Kruskal算法的时间复杂度为O(ElogE)，其中E为边数。 E表示往优先级队列中丢边的过程，而logE表示优先级队列的调整。所以说边越少的复杂度就越低，所以说Kruskal算法适合稀疏图。
Prim算法的时间复杂度是O（N^2），遍历多久是取决于有多少个顶点，如果是稀疏图的话，他的边少，但是他的顶点也不一定少，所以说Prim算法更适合稠密图！！！
总的来说：Prim算法得到的最小生成树是以一个顶点为起点的树形结构，而Kruskal算法得到的最小生成树是以边为基础的森林，需要进行额外的处理（依赖并查集判环）才能形成树。要根据不同的场景去选择。
以下奉上测试代码：
void TestGraphMinTree()
{
const char* str = "abcdefghi";
Graph<char, int> g(str, strlen(str));
g.AddEdge('a', 'b', 4);
g.AddEdge('a', 'h', 8);
//g.AddEdge('a', 'h', 9);
g.AddEdge('b', 'c', 8);
g.AddEdge('b', 'h', 11);
g.AddEdge('c', 'i', 2);
g.AddEdge('c', 'f', 4);
g.AddEdge('c', 'd', 7);
g.AddEdge('d', 'f', 14);
g.AddEdge('d', 'e', 9);
g.AddEdge('e', 'f', 10);
g.AddEdge('f', 'g', 2);
g.AddEdge('g', 'h', 1);
g.AddEdge('g', 'i', 6);
g.AddEdge('h', 'i', 7);
Graph<char, int> kminTree;
cout << "kruskal" << endl << endl;
cout << "kruskal:" << g.Kruskal(kminTree) << endl;
kminTree.Print();
cout << "prim" << endl << endl;
Graph<char, int> pminTree;
cout << "Prim:" << g.Prim(pminTree, 'a') << endl;
pminTree.Print();
} 
二、最短路径
2.1 单源最短路径--Dijkstra算法
单源最短路径问题：给定一个图G = ( V ， E ) G=(V，E)G=(V，E)，求源结点s ∈ V s∈Vs∈V到图中每个结点v ∈ V v∈Vv∈V的最短路径。Dijkstra算法就适用于解决带权重的有向图上的单源最短路径问题，同时算法要求图中所有边的权重非负。一般在求解最短路径的时候都是已知一个起点和一个终点，所以使用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 的代价之和，否则维持原样。如此一直循环直至集合Q 为空，即所有节点都已经
查找过一遍并确定了最短路径，至于一些起点到达不了的结点在算法循环后其代价仍为初始设定
的值，不发生变化。Dijkstra算法每次都是选择V-S中最小的路径节点来进行更新，并加入S中，所
以该算法使用的是贪心策略。
Dijkstra算法存在的问题是不支持图中带负权路径，如果带有负权路径，则可能会找不到一些路径的最短路径
//时间复杂度 O(N^2) 空间复杂度O(N)
void Dijkstra(const V& src, vector<W>& dist, vector<int>& pPath) //src表示起点， dist表示最短路径 path表示父路径(可以帮助我们找到当前记录权值所经过的全部路径)
{
//先初始化一下我们的数组
size_t srci = GetVertexIndex(src);
size_t n = _vertexs.size();
dist.resize(n, MAX_W);
pPath.resize(n, -1);
dist[srci] = W();//给一个初始值，方便第一次找到这个节点
//需要设置一个bool数组帮助我们确定已经确定的最短路径的集合
vector<bool> s(n);
//先去我的各个路径去更新一下 一方面是去更新我们的dsti 一方面去找到最短的顶点u
for (size_t i = 0; i < n; ++i) //一次走一个顶点 走n次
{
W min = MAX_W;//记录最小权重
size_t u = srci;//记录最小顶点
//先找到起点
for (size_t j = 0; j < n; ++j)
if (s[j] == false && dist[j] < min)
{
min = dist[j];
u = j;
}
s[u] = true;//表示确定了点
//以这个往外做松弛操作 更新一遍u连接的所有边 看看有没有可以更新的
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;
}
}
}为了方便测试，实现一个打印路径的函数
void PrinrtShotPath(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) continue;
vector<int> path;
size_t parenti = i;
while (parenti != srci)
{
path.push_back(parenti);
parenti = pPath[parenti];
}
path.push_back(srci);
reverse(path.begin(), path.end());
for (auto& index : path)
cout << _vertexs[index] << "->";
cout << "权值和:"<<dist[i];
cout << endl;
}
}给大家附上测试代码
void TestGraphDijkstra()
{
/*const char* str = "syztx";
Graph<char, int, INT_MAX, true> g(str, strlen(str));
g.AddEdge('s', 't', 10);
g.AddEdge('s', 'y', 5);
g.AddEdge('y', 't', 3);
g.AddEdge('y', 'x', 9);
g.AddEdge('y', 'z', 2);
g.AddEdge('z', 's', 7);
g.AddEdge('z', 'x', 6);
g.AddEdge('t', 'y', 2);
g.AddEdge('t', 'x', 1);
g.AddEdge('x', 'z', 4);
vector<int> dist;
vector<int> parentPath;
g.Dijkstra('s', dist, parentPath);
g.PrinrtShotPath('s', dist, parentPath);*/
//图中带有负权路径时，贪心策略则失效了。
// 测试结果可以看到s->t->y之间的最短路径没更新出来
const char* str = "sytx";
Graph<char, int, INT_MAX, true> g(str, strlen(str));
g.AddEdge('s', 't', 10);
g.AddEdge('s', 'y', 5);
g.AddEdge('t', 'y', -7);
g.AddEdge('y', 'x', 3);
vector<int> dist;
vector<int> parentPath;
g.Dijkstra('s', dist, parentPath);
g.PrinrtShotPath('s', dist, parentPath);
}
2.2 单源最短路径--Bellman-Ford算法
Dijkstra算法只能用来解决正权图的单源最短路径问题，但有些题目会出现负权图。这时这个算法就不能帮助我们解决问题了，而Bellman—ford算法可以解决负权图的单源最短路径问题。它的
优点是可以解决有负权边的单源最短路径问题，而且可以用来判断是否有负权回路。它也有明显
的缺点，它的时间复杂度 O(N*E) (N是点数，E是边数)普遍是要高于Dijkstra算法O(N²)的。像这里
如果我们使用邻接矩阵实现，那么遍历所有边的数量的时间复杂度就是O(N^3)，这里也可以看出
来Bellman-Ford就是一种暴力求解更新
bool BellmanFord(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);
dist[srci] = W();//给一个初始值，方便第一次找到这个节点
bool flag = false;
for (size_t k = 0; k < n; ++k) //按道理来说只需要进行n-1次必然就不需要松弛了
{
flag = false;//前置为false
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])
{
dist[j] = dist[i] + _matrix[i][j];
pPath[j] = i;
flag = true;
}
if (flag == false) break;//如果没有发生松弛
}
//但是还得检查负权值回路
//循环的最后一趟就是用来检查负权值的，如果最后一趟后flag仍为true 说明就有负权回路 应该return false 负权回路神仙难救
return !flag;
}然后附上测试代码：
void TestGraphBellmanFord()
{
const char* str = "syztx";
Graph<char, int, INT_MAX, true> g(str, strlen(str));
g.AddEdge('s', 't', 6);
g.AddEdge('s', 'y', 7);
g.AddEdge('y', 'z', 9);
g.AddEdge('y', 'x', -3);
//g.AddEdge('y', 's', 1); // 新增
g.AddEdge('z', 's', 2);
g.AddEdge('z', 'x', 7);
g.AddEdge('t', 'x', 5);
g.AddEdge('t', 'y', 8);//更改 8变成-8
g.AddEdge('t', 'z', -4);
g.AddEdge('x', 't', -2);
vector<int> dist;
vector<int> parentPath;
if (g.BellmanFord('s', dist, parentPath))
g.PrinrtShotPath('s', dist, parentPath);
else
cout << "存在负权回路" << endl;
// 微调图结构，带有负权回路的测试
//const char* str = "syztx";
//Graph<char, int, INT_MAX, true> g(str, strlen(str));
//g.AddEdge('s', 't', 6);
//g.AddEdge('s', 'y', 7);
//g.AddEdge('y', 'x', -3);
//g.AddEdge('y', 'z', 9);
//g.AddEdge('y', 'x', -3);
//g.AddEdge('y', 's', 1); // 新增
//g.AddEdge('z', 's', 2);
//g.AddEdge('z', 'x', 7);
//g.AddEdge('t', 'x', 5);
//g.AddEdge('t', 'y', -8); // 更改
//g.AddEdge('t', 'z', -4);
//g.AddEdge('x', 't', -2);
//vector<int> dist;
//vector<int> parentPath;
//if (g.BellmanFord('s', dist, parentPath))
// g.PrinrtShotPath('s', dist, parentPath);
//else
// cout << "存在负权回路" << endl;
}
2.3 多源最短路径--Floyd-Warshall算法
Floyd-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}取得的一条最短路径。
注：其实多源最短路径按照Dijkstra算法或者是Bellman-Ford算法以所有点为起点也可以解决这个问题，但是前者不能解决负权值，后者的效率太低，因此都不够完美，所以才需要Floyd-Warshall算法来帮助我们解决多源最短路径问题，其实本质上是一种动态规划思想。
Floyd算法本质是三维动态规划，D[i][j][k]表示从点i到点j只经过0到k个点最短路径，然后建立
起转移方程，然后通过空间优化，优化掉最后一维度，变成一个最短路径的迭代算法，最后即得
到所以点的最短路。
void FloydWarshall(vector<vector<W>>& dist, vector<vector<int>>& pPath) //二维权值矩阵和父路径矩阵
{
//初始化 权值和父路径矩阵
size_t n = _vertexs.size();
dist.resize(n);
pPath.resize(n);
for (size_t i = 0; i < n; ++i)
{
dist[i].resize(n,MAX_W);
pPath[i].resize(n,-1);
}
//先将已有相连的边初始化到dist数组中
for (size_t i = 0; i < n; ++i)
for (size_t j = 0; j < n; ++j)
{
if (_matrix[i][j] != MAX_W)
{
dist[i][j] = _matrix[i][j];
pPath[i][j] = i;
}
if (i == j) dist[i][j] = W();//方便和图对比，并且0不会影响其他路径
}
//利用k作为中间结点，去动态规划更新i->j的路径
for (size_t k = 0; k < n; ++k)
{
for (size_t i = 0; i < n; ++i)
for (size_t j = 0; j < n; ++j)
if (dist[i][k] != MAX_W && dist[k][j] != MAX_W && dist[i][k] + dist[k][j] < dist[i][j])
{
dist[i][j] = dist[i][k] + dist[k][j];
pPath[i][j] = pPath[k][j];//这里要填的是j的上一个邻接顶点
}
//打印权值和路径矩阵观察数据 ctrl+k ctrl+f 自动格式化
// 打印权值和路径矩阵观察数据
for (size_t i = 0; i < n; ++i)
{
for (size_t j = 0; j < n; ++j)
if (dist[i][j] == MAX_W) printf("%3c", '*');
else printf("%3d", dist[i][j]);
cout << endl;
}
cout << endl;
for (size_t i = 0; i < n; ++i)
{
for (size_t j = 0; j < n; ++j)
printf("%3d", pPath[i][j]+1);//方便和图对比
cout << endl;
}
cout << "=================================" << endl;
}
}注意事项：
1，为什么要把邻接矩阵的结果导入到dist中？
其实本质上是为了去玩动态规划的逻辑，将邻接矩阵中直接相连的边先初始化到dist中，然后dist才能按照上面的动态转移方程去更新
2,i->j 按道理来说中间结点最多只可能是n-2个结点，但是为什么在这个地方还是要用n个顶点去尝试呢？？？ 以及为什么i==j的时候dist[i][j]要=0
因为i和j是变化的 比如说abcdef a->f 按道理来说a和f不需要尝试，但是如果下一次是b-d,那a和f也是要尝试的，所以我们这边相当于是自己也要跟自己尝试,所以当i==j的时候dist[i][j]要=0(其实是为了和算法导论的图左对比) 其实本质上就相当于是动态规划中的通过初始化虚拟结点保证不影响其他路径的权值结果 比如a->f 我们拆分a->a 以及a->f ，那么a->a就是0的话是不会影响实际结果的！！！
3，为什么pPath[i][j] = pPath[k][j]而不是=k,因为我们将i->j 拆分成了i->k k->j 但是我们的pPath[i][j]其实要存的是j的上一个邻接顶点，但是k未必就是k的上一个邻接顶点，所以不能是k，但是我们可以从以k为起点到j的路径中去寻找j的上一个邻接顶点， 比如k->j是直接相连，那么pPath[k][j]存的就是k 但是如果k->j不是直接相连，比如说k->……>j ，那么pPath[k][j]存的就是j的上一个邻接结点
附上测试代码：
void TestFloydWarShall()
{
const char* str = "12345";
Graph<char, int, INT_MAX, true> g(str, strlen(str));
g.AddEdge('1', '2', 3);
g.AddEdge('1', '3', 8);
g.AddEdge('1', '5', -4);
g.AddEdge('2', '4', 1);
g.AddEdge('2', '5', 7);
g.AddEdge('3', '2', 4);
g.AddEdge('4', '1', 2);
g.AddEdge('4', '3', -5);
g.AddEdge('5', '4', 6);
vector<vector<int>> vvDist;
vector<vector<int>> vvParentPath;
g.FloydWarshall(vvDist, vvParentPath);
// 打印任意两点之间的最短路径
for (size_t i = 0; i < strlen(str); ++i)
{
g.PrinrtShotPath(str[i], vvDist[i], vvParentPath[i]);
cout << endl;
}
}
写代码一定要想办法去检验!!
关于图论的相关算法就讲解到这里了，感谢大家的支持！！
