个人笔记，仅供复习
1.Bellman-Ford算法
1.1 适用范围：含负权边的带权有向图的单源最短路问题。不能处理带负权边的无向图
1.2 限制条件：要求图中不能包含权值总和为负值回路（负权值回路），如下图所示：
1.3 算法思想：
1.3.1 构造dist[k][u]：算法构造了一个最短路径长度序列dist[k][u]。其中：
- dist[1][u]是从源点v到终点u的只经过一条边的最短路径长度，并有dist[1][u] = Edge[v][u]
- dist[2][u]为从源点v最多经过两条边到达终点u的最短路径长度
- dist[3][u]为从源点v出发最多经过不构成负权值回路的三条边到达终点u的最短路径长度
- dist[n-1][u]为从源点v出发最多经过不构成负权值回路的n-1条边到达终点u的最短路径的长度
算法的最终目的是计算出dist[n-1][u]，为源点v到顶点u最短路径长度。
1.3.2 计算dist[k][u]：采用递推的方式计算dist[k][u]
- 设已经求出dist[k-1][u],u = 0,1,2...,n-1;此即从源点v最多经过不构成负权值回路的k-1条边到达终点的最短路径长度
- 从图的邻接矩阵可以找到各个顶点j到达顶点u的距离Edge[j][u]，计算min{dist[k][j]+Edge[j][u]}，可得从源点v绕过各顶点，最多经过不构成负权值回路的k条边到达终点u的最短路径长度
- 比较dist[k-1][u]和min{dist[k][j]+Edge[j][u]}，取较小者作为dist[k][u]的值
1.3.3 递推公式：dist[1][u] = Edge[v][u]
dist[k][u] = min{ dist[k-1][u] ,min{dist[k][j]+Edge[j][u]} },j = 0,1,...,n-1；j!=u
1.3.4 空间优化：由于计算出来dist[k][u]之后，dist[k-1][u]就没用了，所以我们可以只开一个一维数组dist[u]来不断更新它的值，算法结束时dist[u]中存放的就是dist[n-1][u]。
1.4 代码实例：
#define MAX_VER_NUM 10 //顶点个数最大值
#define MAX 1000000
int Edge[MAX_VER_NUM][MAX_VER_NUM]; //图的邻接矩阵
int vexnum; //顶点个数
int path[MAX_VER_NUM]; //path[i]是i在最短路径中的上一个节点
void BellmanFord(int v) //假定图的邻接矩阵和顶点个数已经读进来了
{
int i, k, u;
for(i=0; i<vexnum; i++)
{
dist[i]=Edge[v][i]; //对dist[ ]初始化
if( i!=v && dist[i]<MAX ) path[i] = v; //对path[ ]初始化
else path[i] = -1;
}
for(k=2; k<vexnum; k++) //从dist1[u]递推出dist2[u], …,distn-1[u]
{
for(u=0; u< vexnum; u++)//修改每个顶点的dist[u]和path[u]
{
if( u != v )
{
for(i=0; i<vexnum; i++)//考虑其他每个顶点
{
if( Edge[i][u]<MAX &&
dist[u]>dist[i]+Edge[i][u] )
{
dist[u]=dist[i]+Edge[i][u];
path[u]=i;
}
}
}
}
}
}1.5 Bellman算法与Dijkstra算法区别：
- Dijkstra算法在求解过程中，源点到集合S内各顶点的最短路径一旦求出，则之后不变了，修改的仅仅是源点到T集合中各顶点的最短路径长度。
- Bellman算法在求解过程中，每次循环都要修改所有顶点的dist[ ]，也就是说源点到各顶点最短路径长度一直要到Bellman算法结束才确定下来。
2.SPFA算法
2.1 适用范围：SPFA算法是Bellman算法的改进版，它们是适用范围是相同的
2.2 算法思想：利用队列动态更新最小值
- 设dist[i]代表s到i点的当前最短距离，fa代表s到i的当前最短路径的前一个点的编号。开始时dist初始值无穷大，只有dist[s] = 0，fa全为0。
- 维护一个队列，里面存放所有需要进行迭代的点。初始时队列中只有一个点s，用一个布尔数组记录每个点是否在队列中。
- 每次迭代，取出头节点v，依次枚举从v出发的边v->u，设边长度为len，如果dist[u] > dist[v]+len，则改进dist[u]，将fa[u]记为v，并且由于s到u的最短距离变小了，有可能u可以改进其他的点，所以如果u不在队列里，就把它放进队尾。
- 若一个点的最短路径被改进的次数达到n，则有负权环。可以通过SPFA算法判断图有无负权环。
void spfa(int s){
//dist[n]初始值无穷大
dist[s] = 0;
queue<int> q;
q.push(s);
vis[s] = true;//v在队列里
while(q.empty()){//队列不为空
int v = q.front();
q.pop();
vis[v] = 0;//v已经不在队列中
for(int u = 0;u < n;u++){
if(dist[u] > dist[v]+cost[v][u]){
dist[u] = dist[v] + cost[v][u];
fa[u] = v;
updataTimes[u]++; //更新了多少次
if(vis[u] == 0) q.push(u);
}
}
}
}