https://en.wikipedia.org/wiki/Shortest_path_problem#Algorithms

http://blog.csdn.net/xiazdong/article/details/8193680

one-source

(1)当权值为非负时，用Dijkstra。

(2)当权值有负值，且没有负圈，则用SPFA，SPFA能检测负圈，但是不能输出负圈。

(3)当权值有负值，而且可能存在负圈，则用BellmanFord，能够检测并输出负圈。

(4)SPFA检测负环：当存在一个点入队大于等于V次，则有负环，后面有证明。

=====

https://www.renfei.org/blog/weighted-shortest-path.html

Dijkstra: 不含负权。运行时间依赖于优先队列的实现，如 O((∣V∣+∣E∣)log∣V∣)O((∣V∣+∣E∣)log∣V∣)
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)O(∣V∣3)