dijkstra、SPFA、Bellman-ford、ASP、Floyd-warshall比较
类型 | 算法 | 限制 | 运行时间 | 单源最短路径 | dijkstra | 不含负边 | 依赖优先队列实现，如O(E+VlgV) | SPFA | 无限制（可检测负圈） | O(k∣E∣) (k∣V∣)O(k∣E∣) (k∣V∣) | Bellman-Ford | 无限制（可检测并输出负圈） | O(∣V∣∣E∣)O(∣V∣∣E∣) | ASP | 无圈 | O(∣V∣+∣E∣)O(∣V∣+∣E∣) | 全源最短路径 | Floyd-Warshall | 无限制 | O(∣V∣^3) | 备注：无向图一条边即可为一个圈 |
如果我们只需要一个起点和一个终点，难道不应该比计算一个起点任意终点更节省时间么？答案还真的不是，目前还没有发现比算从源点到所有点更快的算法，所以一个起点一个终点也是用单源最短路径。 | 
转播
