最短路径之贝尔曼-福特算法
基本概念
图：
有顶点和边组成。又分为
有向图：
在这里只能从A到B，不能从B到A。
无向图：
能从A到B，也能从B到A，也可以用下图表示：
还有就是给边加上权重，变成加权图：
权重代表了两个顶点连接的程度，它可以是时间、距离、路费等等，根据实际情况而定。
最短路径：
如上图，从A到D，有三种路径：ABD、AD、ACD。
考虑到边的权重（比如路费），三条线路中最短路径不是两点直连的AD（10），而是ABD（2 3=5）。
负环路：
虽然从现实场景中，人们很难想象边的权重是负数——没听说过走高速从A到B，不用交高速费，还倒找钱的。
但是从理论上来说，还是要考虑负权边的存在，这就导致一个问题：负环路的存在导致无法找出最短路径。
看下图：
从A到A，花费的是0，这是最短路径了，但是因为有了负权边的存在，会造成：
A-B-C-A，权重为2 2-5=-1，也就是说A绕了一圈，变成-1，比0小，最短路径是ABCA了。
这还没完，再绕一圈，-1 2 2-5=-2，A变成了-2，照此循环下去，A到A的权重会越来越小。
这就是负环路，永远找不到最短路径。
当然，有负权边不代表一定有负环路，如下图：
这就没有形成负环路，A到C的最短路径就是ABC=3
广度搜索优先：
简单地说，就是从根节点开始，搜索完其子节点后，再搜索子节点的子节点，直至找到目标节点或所有节点都被遍历一遍。
如上图，将根节点A的子节点BCD放入队列，取出B，再将B的子节点EF放入队列，接着取出C，再将C的子节点G放入队列，按照队列先进先出的特性，遍历所有节点。
深度搜索优先：
从根节点开始，搜索完一条分支后，再搜索另一分支。
如上图，取根节点A压入栈。
取出A，获取A的子节点BCD，压入栈。
取出B，获取B的子节点EF，压入栈。
取出F，并无子节点，且不是目标节点，抛出。E同理。
取出C，获取C的子节点G，压入栈。
取出G，同F。
取出D，获取D的子节点H，压入栈。
取出H，同F。
松弛操作：
如上图，算出A到D的最短路径。
一开始我们只知道A到A的路径是0，到BCD的路径未知，就设为∞。
计算A-D路径为0 10=10 <∞，故将D由∞改为10。这就是一次松弛操作。
贝尔曼-福特算法
简单地说，就是对图中所有订单、所有边都进行松弛操作，直到找到最短路径。所以其时间复杂度应该是O（顶点数*边数）。
伪代码应该是：
for(int i=0;i<顶点数-1;i ){ for(int j=0;j<边数;j ){ 松弛操作; }}但在实际情况中，在小于“顶点数-1”次的遍历中，已经求出了最短路径，所以在内部循环结束后，校验一下有没有进行松弛操作，如果没有，则说明已求出最短路径，直接跳出即可。
伪代码：
for(int i=0;i<顶点数-1;i ){ 是否进行了松弛操作=false; for(int j=0;j<边数;j ){ if(终点权重>起点权重 边权重){ 松弛操作：终点权重=起点权重 边权重;终点的起点设为起点名称; 是否进行了松弛操作=true; } } if(没有进行松弛操作){ break; }}再结合之前谈到的负环路，在执行完最多顶点数-1次循环后，理应得到最短路径，如果我们额外再遍历一次所有的边，看看有没有进行松弛操作。如果有，说明存在负环路。
添加伪代码：
是否存在负环路=false;for(int j=0;j<边数;j ){ if(终点权重>起点权重 边权重){ 是否存在负环路=true; break; }}操作步骤：
如上图，共有5个顶点：ABCDE。
16条边（无向图，每条线代表两个边）：AB、AC、AD、BA、BC、BE、CA、CB、CD、CE、DA、DC、DE、EB、EC、ED
以A为起点，计算到其他顶点的最短路径。
初始状态下，A的权重应为0，其他节点皆为∞。
1、处理AB，B的权重改为1。此时A=0，B=1，其余为∞。B的起点为A。
2、处理AC，C的权重改为7。此时A=0，B=1，C=7。C的起点为A。
3、处理AD，D的权重改为6。此时A=0，B=1，C=7，D=6。D的起点为A。
4、处理BA，BA=1 1=2>0，无须进行松弛操作。
5、处理BC，BC=1 1=2<7，C的权重改为2，此时A=0，B=1，C=2，D=6。C的起点改为B。
6、接着继续处理，本次对所有边的循环，得出如下结果：
A到各点最低消耗：A=0，B=1，C=2，D=6，E=4
各点的起点：B<--A，C<--B，D<--A，E<--C。
7、接着开启下一轮对所有边的循环，在此次循环中，没有进行松弛操作，故跳出循环。
8、判断没有负环路，至此得出最终结果。