最短路径
BFS求无权图的单源最短路径
简介
直接进行广度优先遍历
使用两个数组，一个记录最短路径值，一个记录到这个顶点的直接前驱
只能用无权图
迪杰斯特拉算法
简介
dijkstra算法是一种一步一步找出最短路径的方法，核心思路就是从初始点开始，一步一步从已确定路径中选取最短的路径作为新的最短路径，并加入新已确定顶点，然后执行多次
实现
我们选用三个数组，分别是标记各顶点是否已找到最短路径的finals，最短路径长度的dist，以及记录路径上的前驱的path
也就是我们每次将可到达的结点找出来，从可获取路径中找到最短路径，并将其前驱记录，标记出结点
时间复杂度为O(n^2)即O(|V|^2)
如果用于负权值带权图，则迪杰斯特拉算法可能会失效
弗洛伊德算法
简介
Floyd算法是求出每一对顶点之间的最短路径 使用动态规划思想，将问题的求解分为多个阶段
对于个顶点的图G,求任意一对顶点Vi一>Vj之间的最短路径可分为如下几个阶段：#初始：不允许在其他顶点中转，最短路径是？ #0:若允许在Vo中转，最短路径是？ #1:若允许在Vo、V1中转，最短路径是？ #2:若允许在Vo、V1、V2中转，最短路径是？ ...... #n-1:若允许在Vo、V1、V2.Vn-1中转，最短路径是？
例如这样，左边的矩阵就是初始时，不中转获得的个顶点建最短路径长度，右边的矩阵是初始时中转点的记录，因为不中转，所以是-1
若允许在V0中转，则新加一
编辑
如此经历n轮递推
woc，大道至简，本身以为是只有一个节点做中转的情况，但是仔细一想，它并不是单源的算法，而是点到点的算法，并且也从来不是每次加一个这么简单，他是考虑了所有的结点
就好比是需要经过 0 2 4 6才能到这个点，在查找时0->2是最小值不需要中转,0->4是经过2的中转，0到6是经过4的中转，但是到4的中转前已经中转过2了,所以这种算法已经考虑了所有的情况
DAG
简介
有向无环图简称DAG 图
DAG描述表达式
相同部分可以合并
节省存储空间
顶点中不能出现重复的操作数，标出来各个运算符的生效顺序，注意分层