目录
Dijkstra
原理：基于贪心。
为什么 Dijkstra 不能处理有负边的情况
Bellman-ford
原理：动态规划， 实质见floyd的另一篇博客
1，能找负环，
2，有变数限制的最短路径
spfa
原理
spfa怎么求负环，
Dijkstra
原理：基于贪心。
第一步
初始化距离，dist[1] = 0, 一号点到起点的距离为0， 其他点到起始点的距离为正无穷 INF。
第二步
是一个迭代的过程for循环n次 i 从0到n ， 现有一个集合S，S里存所有当前已确定最短距离的点，每次循环找到不在S中距离最近的点t，将 t 加入S中。
第三步
用t来更新其他点的距离，更新的方式，从t出去的所有的边，他组成的路劲能不能更强其他点的距离，假设 t 能走到 x ，看当前一号点到 x 的距离能不能用 t 到 x 的距离更新
1 ------> t ----->x 实则看 dist[x] > dist[t] + w[t][x] ( t 到 x 的权重）
每次迭代即循环就能确定一个点的最短距离循环n次确定n个点的最短距离，就能确定每个点到起点的最短距离。
int dijkstra()
{
// 初始化， 一号点到起点的距离为0， 其他点到起点的距离为正无穷
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for(int i = 0; i < n -1; i ++) // n - 1迭代
{
int t = -1;
// 找到未加到 st 集合的最短距离
for(int j = 1; j <= n ; j ++)
if( !st[j] && (t == -1 || dist[t] > dist[j]) )
t = j;
// 将t点加入到集合
st[t] = true;
// 更新从t出去的所有的边，他组成的路劲能不能更强其他点的距离
for(int j = 1; j <= n; j++)
dist[j] = min(dist[j], dist[t] + w[t][j]);
}
}为什么 Dijkstra 不能处理有负边的情况
Dijkstra算法的3个步骤
1、找到当前未标识的且离源点最近的点t
2、对t号点点进行标识
3、用t号点更新其他点的距离
反例
结果：
dijkstra算法在图中走出来的最短路径是1 -> 2 -> 4 -> 5，算出 1 号点到 5 号点的最短距离是2 + 2 + 1 = 5，然而还存在一条路径是1 -> 3 -> 4 -> 5，该路径的长度是5 + (-2) + 1 = 4，因此 dijkstra 算法失效
Bellman-ford
原理：动态规划， 实质见floyd的另一篇博客
能处理还有负权边，
1.迭代 n 次 k从 1 到n，
每次循环所有边 a, b,w，存在一条从a 到 b的边权重为w,
遍历的时候更新，dist[b] = min(dist[b], dist[a] + w),
看一号点走到a在从a 走到b这条路径，比一号点直接走到b的路径短，如果短，将b的路劲更新，
两重循环第一次循环N次，第二重循环，循环所有边，每次循环更新所有边。
bellman - ford算法的具体步骤
for n次
for 所有边 a,b,w (松弛操作)
dist[b] = min(dist[b],back[a] + w)
bellman-ford 证明了所有边的距离一定满足， dist[b] <= dist[a] + w[a][b], （三角不等式）
更新的过程叫松弛操作
迭代具有实际的含义，比如当前迭代K次，则迭代k次之后的dist数组含义为。
从一号点经过不超过K条边走到每个点 的最短距离，
在迭代的时候在第N次时又进行了更新，说明存在一条最短路径，他的最短路径上边的个数大于等于n, 如果一个路径上有n条边，说明有n + 1个点，1到n只有n个点，由抽屉原理，就一定有两个点编号一样，说路径一定存在环，由于这个环更新过所以为负环。
所以，bellman-ford 能找负环，但一般找负环用spfa。
bellman-ford
1，能找负环，
2，有变数限制的最短路径
void bellman_ford()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for (int i = 0; i < k; i ++ )
{
memcpy(last, dist, sizeof dist);
for (int j = 0; j < m; j ++ )
{
auto e = edges[j];
dist[e.b] = min(dist[e.b], last[e.a] + e.c);
}
}
}
spfa
原理
spfa实质是对， bellman-ford进行优化，bellnman-ford每次迭代遍历所有边来更新，但每次迭代不一定每条边都会更新，这个不等式 dist[b] = min ( dist[b] , dist[a] + w[a][b])不一定会把，dist[b]变小，spfa对其优化，
我们每次迭代可以看如果dist[b]想在当次迭代变小，一定是dist[a]变小，因为如果，dist[a]不变小
dist[b]一定不变小，只有a变小，b才可能变小，
dist[b] = min(dist[b], dist[a] + w[a][b])
用宽搜做优化， 迭代的时候用队列，先把起点放入，然后只要队列不空，队列里就是每次变小的结点，只要一个结点变小就放入队列，用他来更新一下所有的后继，比如t结点变小，加入队列，然后用t更新所有以t为起点的边，如果变小在加入队列，加入之前进行判断，如果队列里已经有，就不用在加入，只要队列不空，只要队列里还有结点变小，就进行迭代，
基本思路，更新过谁，再拿谁来更新别人，一个点如果没有更新过在拿这个点来更新别人是肯定没有效果的，只有我变小了，那么我后面的人才会变小。
int spfa()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
queue<int> q;
q.push(1);
st[1] = true;
while (q.size())
{
int t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
if (!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}
}
spfa怎么求负环，
求负环思路与bellman-ford的思路一样运用抽屉原理，在更新dist数组的时候，dist[x],表示的是当前一号点到x点的最短路径的长度，然后记录cnt[]数组,表示当前最短路的边数，每一次更新dist的时候dist[x] =dist[t] + w[t],也更新cnt[t] + 1,更新了dist[x]说明，从一号点到x的距离大于一号点到t的距离加上t到x的距离，所以当前点x的最短路的边数等与t的对短路的变数加1，同时维护两个数组，文章来源：https://www.toymoban.com/news/detail-440346.html
如果说某次的维护cnt[x]的变数大于等n,就意味这，从1到X至少经过了n条边，经过了n条边就说明了经过了n+ 1个点，由抽屉原理只有n个点一定有两个点的值是相同 的有负环，文章来源地址https://www.toymoban.com/news/detail-440346.html
到了这里，关于单源最短路径（spfa,Dijkstra, bellman-ford）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
