Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

## About the so-called SPFA algorithmzhougelin
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:- Re:About the so-called SPFA algorithm
(1174)
**zhougelin**2010-01-01 05:41:28
Post your reply here: |

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator