[补充]:最短路复习

随着2020的即将到来,似乎越来越忙了(hh,当然不是忙于准备年货,而是忙于补各种作业).
今天下午难得有段闲暇时光,复习一下(之前就没理解透透的吧) 图论中的最短路部分,以
便更好的学习.
最短路算法:
1、Dijkstra（一般）: 通过每次循环找全局最小值进行更新其他节点(时间复杂度:O(n^2))
   Dijkstra（优化）：通过二叉堆(优先级队列)找最小值(队首如果就是最小值的话,我们就不用每次都去寻找最小值了)
                     (时间复杂度:O(mlog(n))
2、Bellman-Ford    ：(后续补充,先学了SPFA,hhhhh)
3、SPFA(Bellman-ford的优化) : 通过队列(类似于BFS,每个点可能出队、入队多次)来实现每个顶点的更新,直到队列
                     为空为止.
                     (时间复杂度(km),其中 k 是一个较小的常数)
4、Floyd（任意两点间的最短路）:
                      (时间复杂度:O(n^3)

下面逐个介绍一下各个算法及实现代码:

1、Dijkstra： 
  优点:优化后的算法时间复杂度相对于其他算法来说较低
  缺点:无法处理有负边权的图(这是重点),也就是目光短浅,具体怎么短浅稍后细说.
  算法流程:
  1、初始化dist[1] = 0,(因为本身到自己的距离是 0 ),其余节点的设置为正无穷大(memset(dist,0x3f,sizeof(dist));
  2、找出一个**未被标记的**、dist[x]最小的节点 x ,然后标记节点 x.
  3、扫描节点 x 的所有出边(x,y,z),也就是所有跟节点 x 相连的边,若dist[y] > dist[x] + z,则使用dist[y] = dist[x] + z进行更新,dist[y].（这里用到了三角不等式的原理）.
  4、重复上述2 ~ 3 个步骤,直到所有节点都被更新.
  用图来理解更清晰:
随着2020的即将到来,似乎越来越忙了(hh,当然不是忙于准备年货,而是忙于补各种作业).
今天