假设顶点是\(V_0到V_5\) 六个点，开始时候是没有连线的，但是已知能互相到达的顶点之间的边权。
步骤是每次从顶点0开始查找，找出距离顶点最短的点，然后标记该点为true,再查询该点能直达的其他点加上边权会不会比原先记录的距离值小--->即更新最短距离；遍历完了所有从该点能到的点后再次回到起点。
树与图的存储
树是一种特殊的图，与图的存储方式相同。
对于无向图中的边ab，存储两条有向边a->b, b->a。
因此我们可以只考虑有向图的存储。
(1) 邻接矩阵：<code>g[a][b]</code> 存储边<code>a->b</code>
(2) 邻接表：
// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
当这个图是n个点 m条边的无向图时，那么<code>m可能和 n的2倍差不多</code>:
这时， 不妨设<code>M = 2 * N</code>
<code>h[N]</code> <code>e[M]、ne[M]</code>
时间复杂度<code>O(n+m)</code>,n表示点数，m表示边数
(1)深度优先遍历
(2)宽度优先遍历
朴素版dijkstra算法适合稠密图，用邻接矩阵存储
堆优化版适合稀疏图，用邻接表存储 点的范围较大--稀疏图
时间复杂是 \(O(n^2+m)\), n 表示点数，m 表示边数
1、当到一个时间点时，图上部分的点的最短距离已确定，部分点的最短距离未确定。
2、选一个所有未确定点中离源点最近的点，把他认为成最短距离。
3、再把这个点所有出边遍历一边，更新所有的点。
算法设计：贪心
st[]更确切的含义是某个点是否已经更新过其他点，st最短路确定而不是它的最短距离是否已经确定。所以更新其他点的距离时，前面更新过的点也要更新 其实也可以加上<code>if(!st[j])</code>
思路：
集合S中的点表示已经找到最短路径
一些问题：
在更新dist时，有可能两个点重复进堆，有的点它既是a的邻接点又是b的邻接点，这样的点可能会在更新a的邻接点时加进一次，右在更新b的邻接点的时再进入一次，这样队列中就有两个一样的点，虽然距离不同，所以用<code>st</code> 数组对已经找出最短路径的点进行标记，避免重复计算
题目：有边数限制的最短路a
单源最短路径算法
对于带权有向图 G = (V, E)，Dijkstra 算法要求图 G 中边的权值均为非负，而 Bellman-Ford 算法能适应一般的情况（即存在负权边的情况）。一个实现的很好的 Dijkstra 算法比 Bellman-Ford 算法的运行时间要低。
设计：动态规划
时间复杂度：\(O(V*E)\) 顶点数 边数, \(n顶点数，m边数\)
理解：对所有边进行\(n-1\)次松弛操作,因为在一个含有n个顶点的图中，任意两点之间的最短路径最多包含n-1条边，
换句话说，第1轮在所有边进行松弛后，得到的是源点最多经过1条边到达其他顶点的最短距离；
第2轮在对所有的边进行松弛后，得到的是源点最多经过2条边到达其他顶点的最短距离；
算法描述：
1、\(dist[N]\)数组表示源顶点到所有顶点的距离，初始化为\(infinte\),\(dist[1][1]=0\),
2、计算最短路径，执行\(V-1\)次遍历
对于图中的每条边：如果起点到u的距离d加上权值w小于到终点v的距离，更新终点v的距离值d
\(if(dist[b]>dist[a]+w) dist[b]=dist[a]+w\)
例如以下加上一个拷贝数组就可以求最多经过k条边的最短距离
判断是否有负权环，再对边进行一次额外的遍历，如果还能更新说明仍然存在一条边使得两点距离更短，事实上再更新多次还是有更新的情况。
注意：
如果不限制边数，直接求最短路，不需要拷贝数组
如果限制边数，则需要拷贝数组
为什么是<code>> 0x3f3f3f3f / 2</code> (主要还是因为每条边都遍历了，遍历了很多无用的边)
题目： spafa判断负环
spfa求最短路
https://blog.csdn.net/qq_35644234/article/details/61614581 这篇博客给出了过程
https://www.cnblogs.com/acioi/p/11694294.html spfa求负环的解释
时间复杂度 平均情况下 \(O(m)\)，最坏情况下 \(O(nm)\), n 表示点数，m 表示边数
\(SPFA算法\)是对上面的\(bellmanford\)算法的队列优化
算法描述：首先建立一个队列，初始队列里只有起始点，建立一个表格记录起始点到所有点的最短路径(初始值赋为极大值)，然后进行松弛操作，依次用队列中的点去刷新起始点到所有点的最短路，如果刷新成功且被刷新点不在队列中则把其加入到队列中。
求负环：如果某个点进入队列的次数超过N次则存在负环(N为图的顶点数)
最优解法：用一个cnt[i] 数组记录当前到 到 i 点的最短路径上经过的点的数量，如果 出现<code>cnt[i] > n</code>说明出现了负环。也可统计边数，当<code>边数 >= n</code>时也是出现了负环。
<code>st</code>数组的作用只是记录当前有哪些点在队列中
\(Floyd\)算法属于暴力求解，时间复杂度\(O(n^3)\),\(n\)表示点数
判断无最短路径的方法是<code>> inf / 2</code>, 原因：加入求1~6个点的距离，6是终点，
<code>d[1][5] = 0x3f</code>，1到5不可达，此时 <code>d[5][6] = -4</code>, <code>d[1][6] = d[1][5] + d[5][6] !=0x3f</code>但是大于0x3f/2。此时1到6是不可达的。
题目：有向无环图的拓扑序列
在图论中，拓扑排序是一个有向无环图的所有顶点的线性序列：
1、每个顶点出现一次
2、若存在一条从A到B的路径，那么在序列中顶点A在B的前面。
一个有向无环图一定至少存在一个入度为0的点
如何求拓扑序列？
拓扑序列中，所有的边都是从前往后的，因此入度为0的点都可以作为起点，将所有入度为0的点入队，因为前面没有点指向它，它只能指向后面的点
入队之后，将它指向的终点的入度减去1
入度为0的点入队
遍历t的所有出边
完整模板
![线程同步，可重入锁，synchronized[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)