图的最短路与最小生成树

  最短路:可以分为单起点终点最短路和多起点多终点最短路。它包含了很多算法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) 

图的最短路与最小生成树

  接着,最小生成树。

Prim

Kruskal

上一篇:Dijkstra算法 最短路径


下一篇:Dijkstra算法模板