Shortest Paths Faster - SPFA Algorithm?

Question

I am implementing a k-shortest vertex-disjoint paths algorithm and need a fast algorithm to find the shortest path. There are negative weights so I cant use dijkstra and bellman-ford is O(ne). In a paper I read recently the authors used a so called SPFA algorithm for finding the shortest path in a graph with negative weight, which - according to them - has a complexity of O(e). Sounds interesting, but I cant seem to find information on the algorithm. Appearently this: http://en.cnki.com.cn/Article_en/CJFDTOTAL-XNJT402.015.htm is the original paper, but I dont have access to it.

Does anyone have good information or maybe an implementatin of this algorithm? Also, is there any source for the k-shortest vertex-disjoint paths problem available? I cant find anything.

Thanks!

Answer 1

The SPFA algorithm is an optimization over Bellman-Ford. While in Bellman-Ford we just blindly go through each edge for |V| rounds, in SPFA, a queue is maintained to make sure we only check those relaxed vertices. The idea is similar to Dijkstra's. It also has the same flavor with BFS, but a node can be put in the queue multiple times.

The source is first added into the queue. Then, while the queue is not empty, a vertex u is popped from the queue, and we look at all its neighbors v. If the distance of v is changed, we add v to the queue (unless it is already in the queue).

The author proved that SPFA is often fast (\Theta(k|E|), where k < 2).

Here is pseudo code from wikipedia in Chinese, where you can also find an implementation in C.

Procedure SPFA;
Begin
  initialize-single-source(G,s);
  initialize-queue(Q);
  enqueue(Q,s);
  while not empty(Q) do 
    begin
      u:=dequeue(Q);
      for each v∈adj[u] do 
        begin
          tmp:=d[v];
          relax(u,v);
          if (tmp<>d[v]) and (not v in Q) then
            enqueue(Q,v);
        end;
    end;
End;