[编程笔记]-Shortest_Circuit_Problem(General)最短路问题总概

#前言
本篇博客主要是总概整个最短路问题的算法一览，并不包括每个算法解析，如有需要，请看左边侧边栏的同分类下文章，毕竟也不多，自行寻找，谢谢。

概念

最短路问题就是求从某点到某点的最短距离。

源点就是起点，汇点就是终点。

单源最短路

边权全为正

朴素Dijkstra

时间复杂度是O(n²)。故多用于稠密图。

堆优化Dijkstra

使用堆优化Dijkstra算法，时间复杂度O(mlogn)。故多用于稀疏图。

存在负权边

Bellman-Ford

时间复杂度O(nm)

SPFA

关于SPFA，它死了

时间复杂度一般O(m)，最坏O(nm)。

多源汇最短路

Floyd

时间复杂度O(n³)。

完结撒花o(￣︶￣)o