### Miyukine's blog

By Miyukine, 2 months ago, ,

Hi! I'd like to do ask the wise men of Codeforces if they know any resources related to SPFA (Shortest Path Finding Algorithm). The short description of the algorithm can be found in Princeofpersia's blog:

According to this comment by romanandreev it works on average in $O(m log n)$, but there are counterexamples. Is anyone aware of any papers trying to tackle SPFA complexity?

• +10

 » 2 months ago, # |   -8 It can be made to work in $\mathcal O(nm)$. One of the ways is to construct a graph which looks like a grid.
•  » » 2 months ago, # ^ |   0 Yep, one of these is suggested in the mentioned comment.