Shortest Paths Faster - SPFA Algorithm?

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开发者_JAVA技巧 an implementatin of this algorithm? Also, is there any source for the k-shortest vertex-disjoint paths problem available? I cant find anything.

Thanks!

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;

It is actually a good algorithm to find out the shortest path.It is also regarded as Bellmen-Ford Algorithm rewritten by queue.But in my opinion, it likes BFS.The complexity of it is O(ke)(e means edge-number, k ≈ 2).Though I cannot understand it at all,it is fast in most of problems,especially when there are only a few edges.

Func spfa(start, to) {
  dis[] = {INF}
  visited[] = false 
  dis[start] = 0
  // shortest distance
  visited[start] = true 
  queue.push(start)
  // push start point
  while queue is not empty {
    point = queue.front()
    queue.pop()
    visited[point] = false
    // marked as unvisited                    
    for each V from point {
      dis[V] = min(dis[V],dis[point] + length[point, V]);
      if visited[V] == false {
        queue.push(V)
        visited[V] = true
      }
    }
  }
  return dis[to]
}

It is also very easy to get path & more Hope I can help you(●—●) From OIer

Bellman-ford can handle negative edges.

SPFA and Bellman-ford is basically the same thing, so it has same worst-case complexity.

SPFA is optimization over Bellman-ford.

Take a look at my personal implementation of SPFA in C++ for PS:

using namespace std;

const int INF = INT_MAX / 4;
struct node { int v, w; };
vector<int> SPFA(int max_v, int start_v, vector<vector<node>>&adj_list) {
    vector<int> min_dist(max_v + 1, INF);
    min_dist[start_v] = 0;
    queue<node> q; q.push({ start_v,0 });
    queue<int> qn; qn.push(0);
    while (q.size()) {
        node n = q.front(); q.pop();
        int nn = qn.front(); qn.pop();
        if (nn >= max_v) { printf("-1\n"); exit(0); }//negative cycle

        if (min_dist[n.v] < n.w) continue;
        min_dist[n.v] = n.w;

        for (node adj : adj_list[n.v]) {
            if (min_dist[adj.v] <= adj.w + n.w) continue;
            min_dist[adj.v] = adj.w + n.w;
            q.push({ adj.v, adj.w + n.w }), qn.push(nn + 1);
        }
    }
    return min_dist;
}

int main()
{
    // N: vertex cnt, M: edge cnt
    int N, M; scanf("%d%d", &N, &M);
    vector<vector<node>> adj_list(N + 1);
    for (int i = 0; i < M; i++) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);  // edge u->v, w:weigt
        adj_list[u].push_back({ v,w });
        //adj_list[v].push_back({ u,w }); in case of undirected graph
    }

    // shortest path from '1' to 'N'
    vector<int> dist = SPFA(N, 1, adj_list);
    printf("%d\n", dist[N]);
    return 0;
}