稠密图 朴素dijkstra 稀疏图 spfa和堆优化dijkstra
稠密图->邻接矩阵存 稀疏图->邻接表存
有负边必须spfa 没有负边最好用dijkstra，dijkstra时间复杂度更稳定 spfa用的比较熟，不如不想ac只能过部分分 用spfa也可以
补充一下，有些题虽然都是正权边，但是只能用spfa不能用dijkstra, 比如说341这道题
这题我没做过呢，我只做了图论最基础的一些题目，后面的还没来得及练习。大佬可否指点一下
没事，多做题，到后面慢慢就明白了，如果单纯求最短路你上面写的没错，但是换种形式比如说求从起点到达其他点经过边的最小值，虽然边权都是正数，但是必须用spfa,因为如果用dijkstra的话，因为如果当前点出队的话，就不再用它更新其他点了，但是如果这个点后面的点权值更小，并且形成个环，又再次到达已经出队的点，由于dijkstra的特性就不再更新其他点了，就不对了，因此只能用spfa,这种多做题慢慢就明白啦~~
感谢大佬 回复的很详细
1
补充一下，有些题虽然都是正权边，但是只能用spfa不能用dijkstra, 比如说341这道题
这题我没做过呢，我只做了图论最基础的一些题目，后面的还没来得及练习。大佬可否指点一下
没事，多做题，到后面慢慢就明白了，如果单纯求最短路你上面写的没错，但是换种形式比如说求从起点到达其他点经过边的最小值，虽然边权都是正数，但是必须用spfa,因为如果用dijkstra的话，因为如果当前点出队的话，就不再用它更新其他点了，但是如果这个点后面的点权值更小，并且形成个环，又再次到达已经出队的点，由于dijkstra的特性就不再更新其他点了，就不对了，因此只能用spfa,这种多做题慢慢就明白啦~~
感谢大佬 回复的很详细
1