How to Make SPFA TLE

2019-3-20 created by AD1024

Introduction

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.

Notations and Definitions

• $V$: the set of all vertice of a graph
• $E$: the set of all edges of a graph
• Chrysanthemum Graph: (this is a Chinese OI slang…) a graph such that there is a vertex that is linked to all other nodes with $|V|-1$ edges
• Chrysanthemum Graph Link: a link that connects several Chrysanthemum Graphs.
• Grid Graph (or Lattice Graph): Just like its name…You can imagine it.

SPFA

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.

Optimizations

There are two (traditional) ways to optimize this algorithm, which are explained here: SPFA

Here are some other derived method for optimizing the algorithm:

1. SLF with fault tolerance: Each time before pushing a node $v$ into the queue, we compute the difference between $dist(o, v)$ and $dist(o, hd)$ where $hd$ is the node that in the front of the queue; if the difference is greater than a certain value, we push it to the back of the queue, otherwise, we push it to the front.
2. mcfx optimization: if it is the $k^{th}$ times we are pushing a node into the queue, we put it directly in the front of the queue, otherwise, we push it to the back. Usually, $k \in [2, \sqrt V]$.

Hacks

Naive SPFA

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.

SPFA with LLL (Large Label Last)

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.

SPFA with SLF (Small Label First)

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.

SPFA with (SLF with fault tolerance)

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.

SPFA with mcfx

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.

Conclusion

SPFA is no longer useful if the data is carefully generated to stuck this algorithm.

Reference

[[1]][1]: https://en.wikipedia.org/wiki/Shortest_Path_Faster_Algorithm#Optimization_techniques “Shortest Path Faster Algorithm”

[[2]][2]: https://www.zhihu.com/question/292283275/answer/484871888 “fstqwq’s Answer on Zhihu”