最短路:可以分为单起点终点最短路和多起点多终点最短路。它包含了很多算法Dijkstra,floyd等等。
当图中,边权全都是正数,一般采用Dijkstra
朴素Dijkstra
它的时间复杂度只和点有关,适用于稠密图(边较多)。一般而言,如果m与n^2是一个级别可以认为是稠密图。
//时间复杂度O(n^2),n是点数
堆优化Dijkstra
适用于稀疏图(边较少)
//时间复杂度O(m*logn) m是边数
存在负权边,可以采用bellman-ford,spfa,Floyd。
bellman-ford
//时间复杂度O(n*m)
spfa
//时间复杂度一般是O(m) 最坏是O(n*m)
以上算法都是用于单起点,单终点最短路
Floyd
适用于多起点,多终点最短路。
//时间复杂度一般是O(n^3)
接着,最小生成树。