... the so-called `SPFA' algorithm is exactly the FIFO implementation of the
Bellman-Ford-Moore algorithm (BFMA). In fact, many authors consider the use
of a FIFO queue as an inherent part of the BFMA, not just a variant. I
believe that the name `SPFA' as perceived in the Chinese programming contest
circle was first coined in an article by some candidate to the Chinese OI
team. The article claimed that the algorithm runs in linear time, which I
think drew the attention of many beginners. The claim was absolutely bogus as
instances that force the algorithm to exhibit quadratic behavior are not
hard to construct. Nevertheless, it managed to give fame to the misnomer,
resulting in widespread misunderstanding.

• 以前一直试图在google scholar搜spfa，无果。原来是这样的，汗 (0) zfy0701 2008-11-11 02:25:54
  • 我一直相信在中国有许许多多奇怪的结构和奇怪的叫法是某些人自创的，当然搜不到…… (0) wywcgs 2008-11-11 11:50:10
    • 你这让我想起曾经有某贴讨论什么“星云算法”，不知道当事人还上不上poj，能否给大家解惑。 (0) richardxx 2008-11-11 12:37:24
      • 听名字好强大 (35) wywcgs 2008-11-11 12:53:58
• re (746) ArXoR 2008-11-11 11:56:14
• re (5) crazyb0y 2008-11-12 14:45:41