SPFA algorithm theorem: When the sh

SPFA algorithm theorem: When the shortest path exists, the above SPFA algorithm must be able to find the shortest path value. Proof: Every time the point is put in the tail of the team, it is achieved through the slack operation. In other words, each queue optimization will reduce the shortest path estimate d [v] at a certain point v. Therefore, the execution of the SPFA algorithm will make the shortest path estimated value d smaller and smaller. Since we assume that there is no negative weight loop in the graph, each node has the shortest path value. Therefore, the algorithm will not be executed indefinitely. As the value of d gradually decreases, the algorithm ends when the shortest path value is reached. The shortest path estimate at this time is the shortest path value of the corresponding node. In fact, if a point enters the queue n times, it means that there is a negative ring in the graph, and there is no shortest path. A very intuitive understanding of the SPFA algorithm is derived from the BFS of unweighted graphs. In the unweighted graph, the path experienced by the first vertex reached by BFS must be the shortest path (that is, the minimum number of vertices passed), so at this In order to avoid the worst case, the more efficient Dijkstra algorithm should be used on the positive weight graph. If a given graph has negative weight edges, algorithms like Dijkstra's algorithm will be useless, and the SPFA algorithm will come in handy. In short, when there is no negative weight loop in the weighted directed graph D, the shortest path must exist. Use array d to record the shortest path estimate for each node, and use adjacency table to store graph D. The method we adopt is the dynamic approximation method: set up a first-in first-out queue to save the node to be optimized, and take out the first node u of the team every time during optimization, and use the current shortest path estimation value of u to leave u The pointed node v performs a relaxation operation. If the estimated shortest path of point v is adjusted, and point v is not in the current queue, point v is put at the end of the queue. In this way, nodes are continuously taken out of the queue to perform slack operations until the queue is empty.