최단 경로 빨리 - SPFA 알고리즘?

Question

k-shortest vertex-disjoint paths 알고리즘을 구현 중이고 가장 짧은 경로를 찾으려면 빠른 알고리즘이 필요합니다. 음수 가중치가 있으므로 dijkstra를 사용하고 bellman-ford는 O (ne)를 사용합니다. 최근에 나는 저자 이 음의 가중치를 가진 그래프에서 최단 경로를 찾는 소위 SPFA 알고리즘을 사용했는데, 이들에 따르면 - O (e)의 복잡성을가집니다. 재미 있지만, 나는 알고리즘에 대한 정보를 찾는 것 같지 않다. Appearently 이 : http://en.cnki.com.cn/Article_en/CJFDTOTAL-XNJT402.015.htm은 원래 종이이지만 액세스 할 수 없습니다.

누구든지 좋은 정보를 갖고 있거나 아마도이 알고리즘의 구현을 가지고 있습니까? 또한 k-shortest vertex-disjoint paths 문제에 대한 정보가 있습니까? 나는 아무것도 찾을 수 없다.

감사합니다.

Answer 1

SPFA 알고리즘은 Bellman-Ford보다 최적화 된 알고리즘입니다. Bellman-Ford에서 우리는 맹목적으로 | V | SPFA에서 대기열은 유지 된 꼭지점 만 확인합니다. 아이디어는 Dijkstra 's와 유사합니다. 또한 BFS와 동일한 맛을 지니지 만 노드는 대기열에 여러 번 넣을 수 있습니다.

소스가 먼저 대기열에 추가됩니다. 그런 다음 큐가 비어 있지 않은 동안 버텍스 u가 큐에서 팝되고 모든 이웃 v를 봅니다. v의 거리가 변경되면 v가 이미 큐에 있지 않으면 큐에 추가합니다. .

저자는 SPFA가 종종 빠르다는 것을 증명했습니다 (\ Theta (k | E |), k < 2). 여기

당신은 또한 C에서 구현을 찾을 수 있습니다 wikipedia in Chinese에서 의사 코드

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; 

Answer 2

사실 또한 벨맨 - 포드 알고리즘으로 간주되는 짧은 path.It을 찾을 수있는 좋은 알고리즘 내 생각으로는 BFS를 좋아한다. 그것의 복잡성은 O (케)이다 (e는 모서리 수, k ≈ 2를 의미한다.) 나는 그것을 전혀 이해할 수 없지만 대부분의 문제에서 빠르다. 특히 가장자리가 거의없는 경우. OIer

에서 - (● ●)

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

내가 당신을 도울 수 희망 & 더 경로를 얻을 수도 매우 간단합니다