Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
Statistical Charts
Submit Problem
Online Status
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
欢迎参加IJCAI 2020麻将智能体竞赛,大奖等你拿!Welcome to IJCAI 2020 Mahjong AI competition with amazing prizes! | 北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

About the so-called SPFA algorithm

Posted by zhougelin at 2010-01-01 05:34:13 and last updated at 2010-01-01 05:35:55
The formal academic reference can be found in the course "Network Optimization" of MIT.
You can achieve it using this link (SES #7, Page 18-20) :
It is just an improvement of Bellman-Ford algorithm, and its worst case complexity is very bad.
Furthermore, it is very easy to construct a data to defeat this algorithm.
Suppose you want the shortest path from vertex 1 to vertex n,
then we can add edge (i, i + 1) with a small random weight for 1 <= i < n (thus the shortest path should be 1-2-...-n),
and randomly add 4n other heavy edges. For this case, the so-called SPFA algorithm will be very slow.

(1) SPFA is just a variation of Bellman-Ford, and SPFA is not its real name.
(2) It works well on random sparse graph, but programming contest should consider the worst case.
(3) Anyway, it is much faster than the original Bellman-Ford,
so it will be very helpful if we want to find the shortest path in graphs containing negative weight edges,
such as min cost flow problem.

Followed by:

Post your reply here:
User ID:


Home Page   Go Back  To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator