Caminhos mais curtos mais rápidos - algoritmo SPFA?

Question

Caminhos mais curtos mais rápidos - algoritmo SPFA?

estou a implementar um algoritmo k-shortest vértice-caminhos disjuntos e preciso de um algoritmo rápido para encontrar o caminho mais curto. Há pesos negativos, por isso não posso. use dijkstra e bellman-ford is o (ne). Em um artigo eu li recentemente os autores usou um algoritmo SPFA para encontrar o caminho mais curto num grafo com peso negativo, que - segundo eles-tem uma complexidade de O(e). Som interessante, mas não consigo encontrar informações sobre o algoritmo. Pertinente presente: http://en.cnki.com.cn/Article_en/CJFDTOTAL-XNJT402.015.htm é o original papel, mas não tenho acesso a ele.

Alguém tem boas informações ou talvez uma implementação deste algoritmo? Além disso, existe alguma fonte para o problema de caminhos de vértice-disjuntos k-shortest disponível? Não consigo encontrar nada.

Obrigado!

1

graph shortest-path

Author: sd_, 2011-10-10

Source

2 answers

score 1 · Answer 1

O algoritmo de SPFA é uma optimização sobre Bellman-Ford. Enquanto em Bellman-Ford nós apenas cegamente passar por cada aresta para| V / rounds, em SPFA, uma fila é mantida para se certificar de que apenas verificamos esses vértices relaxados. A ideia é semelhante à de Dijkstra. também tem o mesmo sabor com BFS, mas um nó pode ser colocado na fila várias vezes.

A fonte é adicionada pela primeira vez na fila. Então, enquanto a fila não está vazia, um vértice u é estourado da fila, e nós olhamos para todos os seus vizinhos v. Se a distância de v for alterada, adicionamos v à fila (a menos que já esteja na fila).

O autor provou que o SPFA é frequentemente rápido (\Theta (k|e|), onde k

Aqui está o pseudo-código de wikipedia em Chinês , onde você também pode encontrar uma implementação em 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;

score 0 · Answer 2

Na verdade é um bom algoritmo para descobrir o mais curto path.It é também considerado como algoritmo Bellmen-Ford reescrito pela fila.Mas na minha opinião, ele gosta do BFS.A complexidade dele é O (ke) (e significa número de aresta, k ≈ 2).Embora eu não possa entender,é rápido na maioria dos problemas,especialmente quando há apenas algumas bordas.

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]
}

Também é muito fácil de obter caminho & mais Espero poder ajudá-lo (● - ●) de OIer