2019.1.30
看到海洋发了图论，我也来学习一下。。。。
做了最短路径的问题，总结一下最短路径·的四种常见算法

---

Dijkstra算法

---

这个算法在数据结构学过

初始化：源的距离dist[s]设为0，其他的点距离设为正无穷大，同时把所有的点的状态设为没有扩展过。
循环n-1次：
在没有扩展过的点中取距离最小的点u，并将其状态设为已扩展。
对于每个与u相邻（有向图只kao虑出度）的点v，执行Relax(u,v)，也就是说，如果dist[u]+w[u,v]<dist[v]，那么把dist[v]更新成更短的距离dist[u]+w[u,v]。此时到点v的最短路径上，前一个节点即为u。
结束。此时对于任意的u，dist[u]就是s到u的距离。

例题 hdoj 1874

---

Bellman-Ford算法

---

步骤
一，初始化所有点。每一个点保存一个值，表示从原点到达这个点的距离，将原点的值设为0，其它的点的值设为无穷大（表示不可达）。
第二，进行循环，循环下标为从1到n－1（n等于图中点的个数）。在循环内部，遍历所有的边，进行松弛计算。
第三，遍历途中所有的边（edge（u，v）），判断是否存在这样情况：d（v） > d (u) + w(u,v)。则返回false，表示途中存在从源点可达的权为负的回路。

for(int k=1;k<=n-1;k++)//遍历点的次数
{
for(int i=1;i<=m;i++)//遍历边的次数
{
if(dis[v[i]]>dis[u[i]]+w[i])//如果从u到v的距离能够通过w这条边压缩路径 就要进行松弛操作
{
dis[v[i]]=dis[u[i]]+w[i];
}
}
}

例题 杭电2544

---

SPFA算法

---

3步

1 初始化阶段除了和Bellman-ford算法相同的地方外，还要加上将源点S入队，并且在判断点是否在队列中的数组上做标记（inside[1] = 1）
2 进行迭代，每次迭代，取出队头的点v，遍历所有与v相连的边，进行松弛操作，如果能够松弛并且该点不在队列中，就将它放入队尾。这样一直迭代下去直到队列变空。
3 若一个点入队次数超过n，则有负权环。、、

例题 同杭电2544

---

Floyd算法

---

for (int k = 1; k <= n; k++)
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (v[i][k] + v[k][j] < v[i][j])
{
v[i][j] = v[i][k] + v[k][j];
}
}
}
}