Bellman-Ford algorithm

After relaxation of each implementation 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 time u, To vertex u Relax all edges of . For example, there is one u->v Edge of , If passed u->v This edge makes the source point to the vertex v The shortest distance of

(dis[u]+e[u][v]<dis[v]), And vertex v Not in current queue , Just put the vertex v Put it at the end of the team .

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 ).

On the vertex u After all the edges of , Just put the vertex u Out of the team .

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 , Use adjacency matrix to store this graph , The details are as follows ：

#include <stdio.h> #define INF 999999 int book[10]; // Initialize to no vertices in queue int que[100];

// 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[10], e[10][10]; int head, tail; // Read in n and m,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; } //

initialization dis array for (i = 1; i <= n; ++i) { dis[i] = INF; } dis[1] = 0; //

initialization dis[1] by 0, Others are ∞ head = tail = 1; que[tail] = 1; //1 No tail++; book[1] = 1;

// sign 1 We're on top while (head < tail) // Loop when queue is not empty { for (i = 1; i <= n; ++i) { if

(e[que[head]][i] != INF && dis[i] > dis[que[head]] + e[que[head]][i]) { dis[i]

= dis[que[head]] + e[que[head]][i]; if (!book[i]) // Vertex not in queue , Join queue { book[i] = 1;

que[tail++] = i; } } } // Out of the team 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 Point 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 in head and tail 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 optimized Bellman-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 optimized Bellman-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 optimized Bellman-Ford Algorithm a graph has negative rings ?

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

Using queue optimized Bellman-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 .