Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《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) :
http://ocw.mit.edu/OcwWeb/Sloan-School-of-Management/15-082JNetwork-OptimizationSpring2003/LectureNotes/index.htm
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:
Password:
Title:

Content:

Home Page   Go Back  To top


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