最短路径算法

名词概念

时间复杂度

参考：https://blog.csdn.net/jsjwk/article/details/84315770

执行当前算法所消耗的时间

大O符号表示法，即 T(n) = O(f(n))

大O符号表示法并不是用于来真实代表算法的执行时间的，它是用来表示代码执行时间的增长变化趋势的。

常见的时间复杂度量级有：

  • 常数阶O(1)
  • 对数阶O(logN)
  • 线性阶O(n)
  • 线性对数阶O(nlogN)
  • 平方阶O(n²)
  • 立方阶O(n³)
  • K次方阶O(n^k)【n的k次方，符号不会敲】
  • 指数阶(2^n)

上面从上至下依次的时间复杂度越来越大，执行的效率越来越低。

空间复杂度

执行当前算法需要占用多少内存空间

空间复杂度也是用大O表示法，比较常用的有：O(1)、O(n)、O(n²)。

有权图

Dijkstra算法

Floyd算法

参考资料

代码实现：

https://blog.csdn.net/qq_34989804/article/details/82149495

概念：

https://blog.csdn.net/ZHUO_SIR/article/details/80628663