Your side is loose: the shortest-circuit Bellman-Ford and SPFA methods

Dijkstra's limitations

In the shortest path problem with weighted graph, our goal is to start from one starting point and find the one that reaches all other nodesShortest path. Whether it is the shortest time-consuming route in traffic navigation or the smallest cost path in financial networks, the core of this problem is alwaysHow to find the optimal solution in complex weight relationships。

The classic algorithm Dijkstra is based on itsGreedy StrategyandPriority queue optimization, becoming the benchmark for solving the shortest path of the non-negative power graph:

• Core idea: Each time you select the node closest to the starting point, gradually "diffusion" outward to confirm the shortest path.
• Time complexity：\(O((V+E)\log V)\)(Priority queue implementation), performs excellently in dense graphs.

But behind this algorithm is aFatal premise——All edges must be non-negative。

Dijkstra's "arrogance" and dilemma
Imagine a scenario like this:

The starting point is\(A\),path\(A \to B \to C\)The total weight of\(3 + (-4) = -1\), and Dijkstra may have confirmed it in advance\(A \to C\)The "shortest path" is the weight\(5\). At this time, the power-bearing side\(B \to C\)The existence of the actual better path is completely ignored.

The fundamental contradictionIn this case, Dijkstra ensures efficiency by "locking" the shortest path of the accessed node, but this "arrogant" deterministic strategy becomes a shackle when facing negative power edges - locked nodes cannot be re-corrected.

The Way to Break the Dark: The Philosophy of Relaxation

"Strong cannot be long, soft cannot be kept." Faced with the challenge of undermining power, we need a kind ofFlexible dynamic updatemechanism. This isSlack operation：

• Core significance: This is the same as the update operation of dijstra. However, in the case of negative edges, the node distance value must be allowed to be repeatedly corrected. Each side\((u, v)\)They may be used repeatedly to update, i.e., "Can I make a shorter way?"
• Dynamic: Unlike Dijkstra's "rigid locking", the slack operation recognizes the path'sUncertainty, approximate the optimal solution through multiple rounds of iterations.

The contradiction between the shortest path and the negative power ring

The shortest path of the "black hole"

The usual shortest-circuit algorithm does not restrict repeated passing through nodes and edges, and it doesn't matter for the positive weight graph. Repeating the edges only increases the weight, which is not beneficial; but for the negative weight graph, the existence of the negative weight ring will directly impact the shortest circuit. Definition of the problem.

In the weighted chart, if there is a loop,The total weight is negative(i.e., the cost of the path will be reduced after a circle of circling), then it is calledThe power ring(Negative Weight Cycle). The mathematical expression is:

For example, the loop in the figure\(A \to B \to C \to A\)The weights are\(2, -3, -1\), the total weight is\(-2\), this is a typical negative power ring.

Once there is an accessible path to a negative-rights ring, the shortest path problem will beLoss of meaning: Each time you bypass the negative weight ring, the total path weight is reduced. In theory, the path can be wrapped around infinitely, resulting in a tendency toward the total weight.\(-\infty\). There is no shortest circuit in this picture.

For example, in the following figure, the slave node\(S\)Depart, pass the path\(S \to A \to B \to C \to A\)After that, every time the loop is detoured\(A \to B \to C \to A\), the total weight is reduced by 2. therefore,\(S\)arrive\(C\)The "shortest path" can be optimized infinitely, with no minimum value in the end.

    -3
  B ←-- C
  |     ↑ 
2 |     | -1
  ↓     |
  A --→ S
     4

Negative ring detection

The existence of the negative power ring challenges our intuitive perception of the "shortest path". In the real world, physical distance cannot be negative, but in abstract problems (such as financial clearing, energy consumption optimization)Negative weights are widely present. For example:

• Financial Network: The transfer fee of A to B is -2 yuan (that is, B actually received +2 yuan).
• Energy recovery system: When the robot moves, energy can be recycled on the downhill section and is considered as a negative weight edge.

Any algorithm that claims to support negative power edges must be equippedNegative power ring detection capability, otherwise it may fall into a dead loop when encountering a negative ring, or output an incorrect result. This detection is essentially an algorithmConvergenceVerification: If there is a negative weight ring in the figure, the algorithm needs to clearly report "no solution", rather than trying to calculate the "shortest path" that does not exist. For example, in network routing protocols, it is necessary to avoid permanent cycling of data packets in the loop due to infinite reduction in path costs.

Bellman-Ford Algorithm

The core of the Bellman-Ford algorithm can be summarized in one sentence:Exhaust all possible path updates。

• Violent relaxation strategy: Perform all edges in the figure\(V-1\)Wheel relaxation operation (\(V\)is the number of nodes)
• Basics of Mathematics: In the graph without negative power ring, the shortest path between any two nodes contains at most\(V-1\)Strip edge

The algorithm carpet-scans all sides. Try updating the shortest path with each edge. As long as there is no negative ring, the shortest path can be at most long.\(V-1\), so the maximum execution\(V-1\)Wheels "carpet slack".

class Graph {
     struct Edge {
         int to, weight, index;
         Edge(int t, int w, int i) : to(t), weight(w), index(i) {}
     };
     vector<vector<Edge>> adj; // Adjacent table
     int n;
 public:
     Graph(int n) : n(n), adj(n) {}

     void addEdge(int u, int v, int w, int i) {
         adj[u].emplace_back(v, w, i);
     }

     vector<int> bellmanFord(int s) {
         vector<int> dist(n, INT_MAX);
         dist[s] = 0;
         for (int i = 0; i < n-1; ++i) {
             for (int u = 0; u < n; ++u) {
                 for (auto &e : adj[u]) {
                     if (dist[u] != INT_MAX && dist[] > dist[u] + ) {
                         dist[] = dist[u] + ;
                     }
                 }
             }
         }

         // Detect negative ring
         for (int u = 0; u < n; ++u) {
             for (auto &e : adj[u]) {
                 if (dist[u] != INT_MAX && dist[] > dist[u] + ) {
                     return {}; // There is a negative ring
                 }
             }
         } return dist;
     }
 };

Even if there is a negative ring, some points may still have the shortest circuit. For the sake of simplicity in the code, if there is a negative ring, the algorithm will be directly terminated. In addition, the condition isFully unnecessary conditions, detects the negative ring that can be reached from the vertex.

Time complexity

• Worst case: Complete picture (\(E=V^2\)) The complexity reaches\(O(V^3)\)
• Space complexity：\(O(V)\)(Only storage node distance is required)

Comparison with Dijkstra algorithm:

Negative Ring Detection: Revelation of Round V

Completed\(V-1\)After the wheel is relaxed, the algorithm will proceedFinal trial: If there is no negative ring, all shortest paths should be determined. If the\(V\)The wheel can still relax, which means there isUnlimitedly optimized paths, that is, the power-bearing ring

SPFA Algorithm: Queue Version Bellman-Ford

Although Bellman-Ford's full-volume relaxation strategy can be finally completed, a large number of invalid relaxation operations were wasted during the process. For example, in the chain structure shown in the figure below:

A → B → C → D → E

Each outer loop can only push the update forward by one node, resulting in a large number of repeated calculations. Only the connected edges of the node that was relaxed last time can cause the next relaxation operation. We can ask back to the idea of ​​gradually extending from the source point, only a certain node\(u\)After the distance is updated, its neighbors\(v\)Only then may update is necessary, so you can use a queue to dynamically maintain the pending nodes to avoid full-picture scanning. Of course, because of the existence of negative power edges, a node may be repeatedly queued.

First, mark the source point distance as 0 and join the queue. After that, the nodes are always taken out of the queue and relax the surrounding edges; if the relaxation is successful, the updated node may also optimize other nodes and join them as well. Until the queue is empty.

The naming of SPFA (Shortest Path Faster Algorithm) is full of drama: proposed by Duan Fanding of Southwest Jiaotong University in 1994, and the original paper was named "The Improved Bellman-Ford Algorithm". Because of its outstanding performance in random data, the algorithm community has given this "nickname".

// ...
 vector<int> spfa(int s) {
     vector<int> dist(n, INT_MAX);
     vector<bool> inq(n, false);
     vector<int> cnt(n, 0);

     queue<int> q;
     dist[s] = 0;
     inq[s] = true;
     (s);

     while (!()) {
         int u = ();
         ();
         inq[u] = false;

         for (auto &e : adj[u]) {
             if (dist[u] != INT_MAX && dist[] > dist[u] + ) {
                 dist[] = dist[u] + ;

                 if (!inq[]) {
                     ();
                     inq[] = true;

                     if (++cnt[] > n) {
                         return {}; // There is a negative ring
                     }
                 }
             }
         }
     } return dist;
 }

efficiency

SPFA is more in line with human intuition and is very efficient on random graphs, close to linearity. But at worst it will still degenerate into Bellman-Ford

SPFA reflectsReactive programmingThoughts:Not predictableWhich sides need to be relaxed,No presetUpdating the maximum number of rounds.

Negative ring detection: Counter

SPFA passedNumber of node enqueuesDetect negative rings, such as maintenance counterscnt[v]Record the number of times each node is enqueued, ifcnt[v] > VIt is determined that there is a negative ring (the principle is the same as BellmanFord. In the graph without negative rings, any node will be relaxed at most.\(V-1\)Second-rate). This condition isFully unnecessary conditions, detects the negative ring that can be reached from the vertex.

Data sensitivity of SPFA

Queue Policy Optimization

We know that SPFA's performance is extremely data-dependent. By setting up a queue scheduling strategy, the following techniques can be used in the project to avoid the impact of extreme data as much as possible:

• SLF (Small Label First): If the distance value is found when a new node is enqueuedLess than the team's first node, then the head of the queue (double-ended queue implementation), otherwise the tail of the queue will be entered.
• LLL (Large Label Last): Current node distance valueGreater than the queue averageWhen reinserting it to the end of the queue, avoiding "stuck" in local inferior paths
• Insert points with more entry times from the end of the team instead of the head of the team, or in turn let the points with the previous few joining team enter from the end of the team
• Random perturbation: with probability\(p\)Insert new node into a random position / swap the team head and tail with probability / sort the queue by probability

These optimizations are essentiallyFinding a balance between the FIFO characteristics of a queue and the greedy characteristics of a priority queue. Make the queue as close as possible to the priority queue and not fall into suboptimal solutions. But they are not complex optimization, they are just trying to deal with common construct data (chrysanthemum diagram, grid diagram). In theory, as long as the queue is still used, there will always be stuck.\(O(VE)\)The worst data.

Queue variant experiment: When SPFA no longer "queue"

Another idea is to replace the data structure, which will cause interesting phenomena:

Experiment 1: Priority queue (Dijkstra that can be re-entered)

• accomplish: Use priority queue (heap) instead of ordinary queue, pressdistance[v]Sort
• advantage：
  • In the positive weight chart, the time complexity is equivalent to Dijkstra,\(O(E \log V)\)
  • For certain specific negative power graphs (such as near DAG graphs) may be faster
• Disastrous consequences：
  • When encountering negative power edges, nodes may be enqueued many times (distance values ​​are repeatedly updated)
  • The complexity is no longer stable and can be constructed to be stuck to exponential complexity.

Experiment 2: Stack (depth priority relaxation)

• accomplish: Use stack instead of queue, last in first out (LIFO)
• advantage：
  • Some negative rings may be discovered sooner (deep priority penetration loops)
  • More efficient chain update structure
• shortcoming：
  • Reduced efficiency on random graphs
  • "Update oscillation" is likely to occur in the non-negative ring chart
  • The complexity is no longer stable and can be constructed to be stuck to exponential complexity.

The FIFO feature of the queue is SPFA inGeneral useandefficiencyThe best balance between the two. Any structural change will break this exquisite balance, unless the data is special, it is better not to move.

Algorithm comparison

The following table shows Dijkstra and Bellman-Ford/SPFAIntrinsic contradictionandComplementary relationship：

Through the three-element decision tree selection algorithm:

1. Is there a negative power edge?
   • None → Dijkstra (stable and efficient)
   • Yes → Enter the next level of judgment
2. Is it necessary to detect negative rings?
   • Need to be tested → Bellman-Ford/SPFA
   • No testing is required → Consider conversion to non-negative powers (Johnson algorithm preprocessing)
3. Graph structure characteristics?
   • Random sparse graph → SPFA (average\(O(E)\)）
   • Dense regular diagram → Bellman-Ford (avoid queue jitter)
   • Dynamic and frequent updates → SPFA (Incremental Processing)

As the "Book of Changes" says: "If you are poor, you will change; if you change, you will be open; if you are continuous, you will be long." Faced with the thousands of changes in the shortest path problem, only by understanding the philosophy behind the algorithm can you find the key to breaking the deadlock between hardness and softness.