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

Re:About the so-called SPFA algorithm

Posted by zhougelin at 2010-01-01 05:41:28
In Reply To:About the so-called SPFA algorithm Posted by:zhougelin at 2010-01-01 05:34:13
我懒得写中文版了。英文很烂,大家将就看吧。
顺祝新年快乐 :)

> 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