kpw29's blog

Resources on SPFA
By kpw29, 5 years ago, In English

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:

picture

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?

  • Vote: I like it
  • +10
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it -8 Vote: I do not like it

It can be made to work in $$$\mathcal O(nm)$$$. One of the ways is to construct a graph which looks like a grid.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yep, one of these is suggested in the mentioned comment.

    → Reply