深度遍历 DFS（Depth First Search）
用到了一个很重要的思想就是回溯。 往往可以通过递归来实现。首先，选定一个出发点v后进行遍历，如果有邻接的未被访问过的节点则继续前进。若不能继续前进，则回退一步再前进，若回退一步仍然不能前进，则连续回退至可以前进的位置为止。重复此过程，直到所有与选定点相通的所有顶点都被遍历。
深度优先搜索是递归过程，带有回退操作，因此需要使用栈存储访问的路径信息。当访问到的当前顶点没有可以前进的邻接顶点时，需要进行出栈操作，将当前位置回退至出栈元素位置。
广度遍历 BFS（Breadth First Search）
可以理解为地毯式地搜索, 一层一层地搜索。
1.访问过的顶点, 不能再访问了
2.要记录到某一顶点前经过的顶点
3.需要层序遍历顶点
迪杰斯特拉算法、迪科斯彻（Dijkstra算法）
迪科斯特拉算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题，算法最终得到一个最短路径树。
Dijkstra算法采用的是一种贪心的策略，声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合：T，初始时，原点 s 的路径权重被赋为 0 （dis[s] = 0）。若对于顶点 s 存在能直接到达的边（s,m），则把dis[m]设为w（s, m）,同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大。初始时，集合T只有顶点s。
然后，从dis数组选择最小值，则该值就是源点s到该值对应的顶点的最短路径，并且把该点加入到T中，OK，此时完成一个顶点，
然后，我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，如果是，那么就替换这些顶点在dis中的值。
然后，又从dis中找出最小值，重复上述动作，直到T中包含了图的所有顶点。
var dis = []; //保存顶点到各顶点的距离
vat T = [];//各顶点是否已被确认最短距离
var route = [];//各顶点入点
弗洛伊德算法（Floyd算法）
弗洛伊德算法是解决任意两点间的最短路径的一种算法。
通过Floyd计算图G=(V,E)中各个顶点的最短路径时，需要引入两个矩阵，矩阵S中的元素a[i][j]表示顶点i(第i个顶点)到顶点j(第j个顶点)的距离。矩阵P中的元素b[i][j]，表示顶点i到顶点j经过了b[i][j]记录的值所表示的顶点。
使用三重循环，用于计算每个点对的最短路径。核心就是，通过插点，判断所有顶点到其他顶点是否能松弛路径长度。
S每行是一个i->j的距离数组，P记录i->j的j前一个路径点。
SPFA
它的原理是对图进行V-1次松弛操作，得到所有可能的最短路径，采用动态逼近法。其优于迪科斯彻算法的方面是边的权值可以为负数、实现简单，缺点是时间复杂度过高，高达 O(VE)。但算法可以进行若干种优化，提高了效率。
用数组dis记录每个结点的最短路径估计值，用邻接表或邻接矩阵来存储图G。采取的方法是动态逼近法：设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。
SPFA 在形式上和广度优先搜索非常类似，不同的是bfs中一个点出了队列就不可能重新进入队列，但是SPFA中一个点可能在出队列之后再次被放入队列，也就是一个点改进过其它的点之后，过了一段时间可能本身被改进(重新入队)，于是再次用来改进其它的点，这样反复迭代下去。
负权环
带有负环的图是没有最短路径的，所以我们在执行算法的时候，要判断图是否带有负环，方法有两种：
开始算法前，调用拓扑排序进行判断（一般不采用，浪费时间）
如果某个点进入队列的次数超过N次则存在负环（N为图的顶点数）
