Worst test case for SPFA

Question

Recently, I have read about Shortest Path Faster Algorithm. I am wondering how to construct a test case for which standard implementation of SPFA wolud be very, very slow. Do you know any?

By standard implementation, I mean this one from Wikipedia:

 procedure Shortest-Path-Faster-Algorithm(G, s)
1    for each vertex v ≠ s in V(G)
2        d(v) := ∞
3    d(s) := 0
4    offer s into Q
5    while Q is not empty
6        u := poll Q
7        for each edge (u, v) in E(G)
8            if d(u) + w(u, v) < d(v) then
9                d(v) := d(u) + w(u, v)
10                if v is not in Q then
11                    offer v into Q

Answer 1

For example. There are N vertices. 1st vertex is the start and Nth vertex is the End. For ith vertex, there is 2 edges: (i, i+1, 1) and (1, i, 2*N) where (a,b,c) means there is an edge from a to b with weight c.

It is easy to see that the shortest path at this graph is 1->2->3->4->...->N. Assume that for the 7th line of your spfa algorithm :for each edge (u, v) in E(G), the vertex with bigger id get accessed before the vertex with smaller id. Then the ith vertex will be push into the queue max(1,i-1) times. So the total execution time is O(N^2).

Further more, if for the 7th line, the vertex with bigger id get accessed later than the vertex with smaller id, then the execution time is O(N).

For spfa, there will always exists a traverse order of the 7th line which leads to the worst time complexity, and always exists a traverse order of the 7th line which leads to the best time complexity. The critical thing is how the information is been spread through the shortest path.