每次复习建议看一遍这个总结再去把基础课中的题全部写一遍。

Dij，Spfa，Bellman-ford，Floyd。

Dij

• 算法流程：每轮用优先队列找到最大的dis[x]，然后更新x周围的点，更新成功就入队。vis[]表示当前点的dis[]是否确定，每次弹出heap的top时如果vis[]为1就continue，否则就vis[] = 1。
• 算法原理：循环n轮，每轮都可以确定一个点的dis[]，n轮后，全部点的dis[]就算好了。
• 算法优点：快且稳定
• 算法缺点：不能存在负边

Spfa

• 算法流程：每轮取出队首x，vis[x] = 0，然后更新x周围的点，更新成功并且不在队中就入队。vis[]表示当前点是否在队列中。
• 算法原理：Bellman-ford中，dis[v] = min(dis[v], dis[u] + w)，只有当dis[u]先变小后，dis[v]才有机会变小，存在一个先后关系。所以用队列来维护这种先后关系减少计算量。
• 算法优点：可以存在负边且还算快
• 算法缺点：不能存在负环，容易被出题人卡

Bellman-ford

• 算法流程：两重循环，第一重循环n次，第二层循环m次。每次dis[v] = min(dis[v], backup[u] + e[j].w)。注意它是一层一层更新的，所以backup就是上一次的dis，滚动数组的感觉。
• 算法原理：不懂
• 算法优点：能做“不超过k条路的最短路”问题
• 算法缺点：慢

Floyd

• 算法流程：dis[][]要先inf，然后dis[i][i] = 0，然后输入时要取min值，然后三重循环。注意因为其更新是全局枚举，不具有“连续性”，所以要多加一个if (dis[i][k] != inf && dis[k][j] != inf) 才能更新，要不然就不能用dis[x][y]是否等于inf来判断是否存在最短路。
• 算法原理：dp
• 算法优点：多源最短路；貌似有一些题转移元素间关系是用Floyd实现；可以存在负边权
• 算法缺点：慢；不能存在负环

题型

1. 普通最短路问题：没有负边权用dij，有的话用spfa
2. 判负环：用spfa。注意超级源点思路；注意dis初始化为0；注意cnt表示由第一次出现的负边起点做起点到某点所经过的路径条数；注意抽屉原理运用
3. 不超过k条路最短路问题：用Bellman-ford。注意其算法第一层循环，循环i次就能求出在路径条数不超过i条前提下，到各个点的最短路；注意backup[]的使用；由于其更新不具有“连续性”（spfa具有），所以要写成if (backup[u] != inf)，这样子结尾才能用dis[n]是否等于inf来判断是否存在最短路。
4. 最短路计数问题：用Dij和spfa都可，加个计数数组就好。

写在最后

感觉图论这一块，y总理论性的证明讲得少了一些。不过由以往的经验可以发现，在考试中，图论本身就不会考察很底层原理，更多的是基于模板的变形。
把算法流程和表面的原理弄懂了就行了，图论题的思维题都是建立在模板之上的。
数据结构题不同，数据结构对于底层原理的理解与是否能解出题目直接挂钩。例如并查集对于树边的运用等等