Bellman-Ford algorithm
After each relaxation in turn, There will be some vertices with the shortest path, Since then, the estimation of the shortest path of these vertices will remain the same, No longer accept the influence of subsequent relaxation operation, But every time we have to judge whether we need to relax, This is a waste of time.

You can learn from it： Relax only all outgoing edges of the vertex whose shortest path estimation changes each time.

but, How to know which shortest distance has changed?

Here you can maintain these points with a queue, The algorithm is roughly as follows：

Pick the top of the team every timeu, Right vertexu Relax all edges of. For example, there is oneu->v Edge, If passedu->v This edge makes the source point to the vertexv The shortest distance of

(dis[u]+e[u][v]<dis[v]), And the vertexv Not in current queue, Will be the vertex.v End of queue.

It should be noted that, It doesn't make sense for the same vertex to appear multiple times in the queue at the same time, So we need an array to judge the weight( Determine which points are already in the queue).

At the vertexu After all the edges of, Will be the vertex.u Team out.

Next, remove the new top of the queue from the queue and perform the above operations, Until the queue is empty.

For the above figure, Using queue optimization to find the shortest path.

Here is the code implementation, Using adjacency matrix to store this graph, As follows：

#include <stdio.h> #define INF 999999 int book; // Initialize to no vertices in queue int que;
// If the relaxation succeeds and the vertex is not in the queue, it will be merged into the queue int main(int argc, char const *argv[]) { int i, j, n, m;
int q1, q2, q3; int dis, e; int head, tail; // Read inn andm,n Represents the number of vertices,m Indicates the number of sides
scanf_s("%d %d", &n, &m); // Initialize adjacency matrix for (i = 1; i <= n; ++i) { for (j = 1; j <=
n; ++j) { if (i == j) { e[i][j] = 0; } else { e[i][j] = INF; } } } // Input edge for (i
=1; i <= m; ++i) { scanf_s("%d %d %d", &q1, &q2, &q3); e[q1][q2] = q3; } //
Initializationdis array for (i = 1; i <= n; ++i) { dis[i] = INF; } dis = 0; //
Initializationdis by0, Others are∞ head = tail = 1; que[tail] = 1; //1 No tail++; book = 1;
// sign1 We're on top while (head < tail) // Loop when queue is not empty { for (i = 1; i <= n; ++i) { if
= dis[que[head]] + e[que[head]][i]; if (!book[i]) // Vertex not in queue, Join queue { book[i] = 1;
que[tail++] = i; } } } // Team out book[que[head]] = 0; // Retag not in queue head++; // Equivalent to leaving the team }
printf(" The final result is：\n"); for (i = 1; i <= n; ++i) { printf(" 1 Vertex to%d The shortest distance between No：%d\n",
i, dis[i]); } printf("\n"); getchar(); getchar(); return 0; }

Here's a summary.
Initially queue source points. Every time I leave the team（head） Take out a vertex, And try to relax all the adjacent vertices, If an adjacent vertex relaxes successfully, And the adjacent vertex is not in the queue（ Be not inhead andtail Between）, Then add it to the queue. Leave the team immediately after processing the current vertex, And operate as above for the next new team leader, Until the end of the queue empty algorithm.

Using queue optimizedBellman-Ford The algorithm is very similar to breadth first search in form, The difference is that in breadth first search, a vertex usually does not re-enter the queue after leaving the queue. And queue optimizedBellman-Ford Algorithm a vertex is likely to be put into the queue again after it leaves the queue, That is, when the shortest path estimation of a vertex becomes smaller, You still need to relax all the edges again, In this way, the shortest path estimation of adjacent vertices can be updated synchronously.

How to judge the optimizedBellman-Ford Algorithm a graph has negative rings?

If a point enters the queue more than oncen second, So there must be a negative ring in this graph.

Using queue optimizedBellman-Ford The key point of the algorithm is： Only those points that changed the shortest path estimate in the previous relaxation, It is possible to cause the estimated value of the shortest distance between their adjacent points to change.

30天阅读排行