SPFA (Shortest Path Faster Algorithm) is a controversial algorithm. The first time it appeared was in 1950s as a generalization of BFS (Wikipedia, para.1). It was later introduced by Fanding Duan, a Chinese professor in Xian Jiaotong University, and he gave a proof that the complexity of SPFA is $O(k|E|)$, where $k$ is a small constant. But the proof later was verified wrong.
Here, based on answers and analysis given by some Chinese high school students on how to make SPFA TLE. The answers are translated by myself, and the copyright belongs to fstqwq and all the people contributed to the original answer.
Restriction: No negative rings in the graph.
Expected Time Complexity: $O(k|E|)$ (The proof in the original paper is wrong)
Worst Case: $O(|V|\cdot|E|)$
To be simple, I won’t elaborate the detail of this algorithm but only present its thought. SPFA (Shortest Path Fast Algorithm) is to basically maintain a queue of nodes that need relax. A node $v$ will be pushed into queue $\iff$ $v$ is not in the queue and $dist(o, v) > dist(o, v^\prime) + dist(v^\prime, v)$, where $dist$ denotes current length of the shortest path between two vertice.
There are two (traditional) ways to optimize this algorithm, which are explained here: SPFA
Here are some other derived method for optimizing the algorithm:
Construct a random grid graph. Since the probability that the algorithm goes into a wrong way is larger than a traditional graph, it will make the relaxation to be frequent and thus can slow down the algorithm. Another approach is to construct a Chrysanthemum Graph Link within a Grid Graph.
Because this optimization compares the average current shortest distance with $dist(o, v)$, where $v$ is the node we are about to push into the queue, we can connect an edge with a very large weight (distance) from $o$ to another node. This will make the optimization have nearly no effect. Then use the common method stated above to make it TLE.
Also, we construct a Chrysanthemum Graph Link. On the link between two Chrysanthemum Graphs, we construct several edges with small weight to lead the algorithm to access the Chrysanthemum Graphs frequently. Thus we can make it TLE.
If the sum of the weight of all edges in the graph is not large, it is hard to make it TLE. With fault tolerance, the tolerance threshold could be $\sqrt |V|$. The way we make it TLE is to use the method stated in above, and make the weight of the edges to be large.
The same way we stuck SPFA with SLF. P.S. combining this optimization with SLF with fault tolerance can make SPFA better and harder to be TLE.
SPFA is no longer useful if the data is carefully generated to stuck this algorithm.
[]: https://en.wikipedia.org/wiki/Shortest_Path_Faster_Algorithm#Optimization_techniques “Shortest Path Faster Algorithm”
[]: https://www.zhihu.com/question/292283275/answer/484871888 “fstqwq’s Answer on Zhihu”