Блог пользователя kpw29

Resources on SPFA
Автор kpw29, 5 лет назад, По-английски

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?

  • Проголосовать: нравится
  • +10
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится -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.

→ Ответить