Differential constrained SPFA

Bellman-Ford Algorithm and Dijkstra The algorithm is the same as the algorithm for solving the shortest path of single source
Bellman-Ford The algorithm uses DP thought , The time complexity is O(V*E),Dijkstra The algorithm adopts greedy strategy , The time complexity of ordinary implementation is O(V2) among V Is the number of vertices ,E For the number of sides .
Dijkstra There is a feature ： Once a vertex is added to S In the after , Its shortest path length will not change , Therefore, it is not suitable for weighted graphs with non negative weights to find the shortest path of a single source
For weighted digraphs G = (V, E),Dijkstra Algorithm requirements diagram G The weights of the middle edges are non negative , and Bellman-Ford The algorithm can adapt to the general situation （ That is, there is a negative weight edge ）

SPFA

Shortest Path Faster Algorithm）（ Queue optimization ） Algorithm is an algorithm for finding the shortest path of a single source , It also has an important function of judging negative rings （ It will be reflected in the differential constraint system ）