It’s happy today!
we learned Dijkstra,Bellman-Ford and SPFA.
1.回顾邻接表
昨天学的，今天忘了
不会发图，不说了。
2.Dijkstra与优化
1.在数组dis[ i ]里查找S[ i ]!=1，并且dis[ i ]最小的顶点k
2.将S[ k ]改为1，表示 k 已经加入S集合中。即已经找到源点v0到点k的最短路径了。
3.修改T集合中每个顶点 j 的dis和path数组元素值：当S[ j ]！=1，且k到顶点 j 有dis[ k ]+e[ k ][ j ] v[i]）权值为w[i]
3.初始化：dis[v0]=0,dis[ i ]=∞（i≠v0）
4.看看能否通过u[i]—>v[i] （权值为w[i]）这条边，使源点到vi号顶点的距离变短。即源点到u[i]号顶点的距离（dis[u[i]]） 加上 u[i] —> v[i]这条边（权值为w[i]）的值是否比原来源点到v[i]号点距离（dis[v[i]]）要小。
只要进行n – 1 轮
可以判断负环
如果一个图没有负权回路，那么最短路径所包含的边最多为n-1条，即进行n-1轮松弛操作后最短路不会再发生变化。如果在n-1轮松弛后最短路仍然可以发生变化，则这个图一定有负权回路
4.SPFA
实际是3.的优化，加了队列。
即每次只将在本次松弛中最短路发生变化的点加入队列中
记源点为v0，vst[ ]记录点是否在队列中，距离值为dis[ ]。
1.初始化：dis[v0]=0，其他点的距离为∞；将源点v0入队，vst[ v0 ]=1
2.从队首取出点k，扫描所有由 k 结点可以一步到达的结点；一旦发现有结点 j 可以松弛，更新dis[ j ]的值，再检查j当前是否在队列中，如果不在，就将 j 入队。
3.重复执行步骤②，直到队列为空