单源最短路
1.dijkstra算法(仅适用于正权图)分为朴素dijkstra算法与堆优化dijkstra算法
(1).朴素dijkstra算法:适用于稠密图,边是点的平方量级,时间复杂度O(n^2)
(2).堆优化dijkstra算法:适用于稀疏图,时间复杂度O(nlogm),
主要依据小根堆的有序性做内层循环中选择最小值从O(n)到O(1)的一个优化,
但是同时也带来了新的问题:堆中无法删除某个点。可以用对点编号并做使用记录的方法解决。
----------
2.负权图中可以使用bellman算法和spfa算法
(1).bellman算法是暴力的两层循环做松弛操作,时间复杂度O(nm)。
(2).spfa算法时间复杂度一般是O(n),最坏O(nm)。spfa算法是相较于bellman算法的一个优化,因为只有在t点取得更
优解之后,t点的出边才需要做松弛操作。因此用队列存储取得过最优解的点,再依次找这些点的出边做松弛操作。同
时要考虑到一个t点可以更新多个点(因为t有不止一个出边可以作为更新数据),所以用st[]判读点是否在队列中。
* 一般可以用spfa代替dijkstra算法,如果卡了则堆优化dijkstra
多源最短路
floyd算法:基于dp思想,用邻接矩阵计算,时间复杂度是O(n^3),可以查询任意两点之间的最短路。
基本做法是通过三层循环将原本存储邻接矩阵的d数组更新成为存储从i到j最短路的数组。