최단 경로 고속 알고리즘

그래프 및 트리쉬 알고리즘
α–β A* B* 역추적 빔 벨먼-포드 베스트 퍼스트 양방향 보르슈프카 분기 & 바운드 BFS 대영 박물관 D* DFS 디크스트라 에드먼즈 플로이드-워셜 프린지 검색 힐 클라이밍 IDA* 반복적 심화 존슨 점프 포인트 크루스칼 사전 BFS LPA* 프라이머리 SMA*
목록
그래프 알고리즘 검색 알고리즘 그래프 알고리즘 목록
관련 항목
동적 프로그래밍 그래프 통과 나무횡단 검색 게임 그래프 컬러링
v t

최단 경로 고속 알고리즘(SPFA)은 Bellman-Ford 알고리즘의 개선으로, 단일 소스 최단 경로를 가중 지시 그래프로 계산한다.알고리즘은 무작위 희소 그래프에서 잘 작동한다고 생각되며 특히 음-가중 에지를 포함하는 그래프에 적합하다.^[1]그러나 SPFA의 최악의 복잡성은 Bellman-Ford와 동일하므로 음이 아닌 에지 가중치를 가진 그래프의 경우 Dijkstra 알고리즘을 사용하는 것이 바람직하다.SPFA 알고리즘은 에드워드 F에 의해 처음 출판되었다. 1959년 폭 1차 탐색을 일반화한 무어;^[2] SPFA는 무어의 '알고리즘 D'이다. 1994년 알고리즘을 재발견한 중국 연구자 판딩 뒤안이 붙인 이름이다.^[3]

알고리즘.

가중 지시된 그래프 $G{\displaystyle }$= (${\displaystyle }$V${\displaystyle }$, ${\displaystyle E}$) ${\displaystyle G=(V,E)}$ 및 소스$$ $꼭지점{\displaystyle }$ s ${\$$displaystyle$ $s$$}$에서$$각 꼭지점 $v{\displaystyle }$ ${\displaystyle v$까지의 최단 경로를 그래프에서 찾는다$.$$s{\displaystyle }$ ${\displaystyle s}$에서 $v{\displaystyle }$ ${\displaystyle v}$까지의 최단 경로 길이는 각 꼭지점 $v{\displaystyle }$ ${\displaystyle v}$에 대해 $d{\displaystyle (v}$ ${\displaystyle )}$ ${\displaystyle d(v)}$에 저장된다$.$

SPFA의 기본이념은 각각의 꼭지점이 인접한 정점을 이완시키기 위한 후보로서 사용된다는 점에서 벨만-포드 알고리즘과 동일하다.후자에 비해 개선된 점은 모든 정점을 맹목적으로 시도하는 대신, SPFA는 후보 정점의 대기열을 유지하고 정점이 이완된 경우에만 정점을 대기열에 추가하는 것이다.이 과정은 더 이상 정점을 풀 수 없을 때까지 반복된다.

다음은 알고리즘의 유사 코드다.^[4]여기서 $Q{\displaystyle }$ ${\displaystyle Q}$은 후보 정점의 첫 번째, 첫 번째 대기열이며, w${\displaystyle (}u{\displaystyle }$ ,${\displaystyle v}$) ${\displaystyle w(u,v$)}은$($u${\displaystyle }$, ${\displaystyle v}$) ${\displaystyle(u,v)}$의 에지 중량이다$.$

절차 Shortest-Path-Faster-Algorithm(G, s)1은 각 꼭지점에 v≠ V(G)2에 sd(v):)∞ 3d(s):=04Q5으로 진출하다. sQ 비어 있는 것이 아니니 6u:= poll Q7E(G)의 각 가장자리(u, v)8더 내더라도 d(u)+w(u, v)<>d(v) 다음 9d(v):)d(u)+w(u, v)10i.fv가 Q에 있지 않고 11에 v를 Q에 푸시

또한 알고리즘은 각 비방향 가장자리를 반대 방향의 두 방향 가장자리로 교체하여 비방향 그래프에도 적용할 수 있다.

정확성 증명

우리는 알고리즘이 결코 부정확한 최단 경로 길이를 계산하지 않는다는 것을 증명할 것이다.

보조정리: 대기열이 비어 있는지 확인될 때마다, 현재 이완을 일으킬 수 있는 정점이 대기열에 있다.

증명: 조건을 확인할 때 두$$ 꼭지점 $u{\displaystyle }$ ${\displaystyle u}$과($)$ w {\$displaystyle$u에 대해 d i [$w$+ w$(u$w$)}$이(가) 있으면 ${\displaystyle }$ ${\displaystyle u}$이(가) 대기열에 있음을$$ 보여주고자 한다.우리는 이미 발생한 루프의 반복 횟수를 유도함으로써 그렇게 한다.먼저, 루프가 입력되기 전에 확실히 이 기능이 유지된다는 점에 주목한다. ${\displaystyle u}$ ${\displaystyle \ne }$ s ${\displaystyle u\not=s},$$u{\displaystyle }$= ${\displaystyle s}$ ${\displaysty u=s},$ 그리고 이것은 루프가 입력되기 직전에 대기열에 추가된다.이제, 루프 안에서 무슨 일이 일어나는지 생각해봐.정점 $u{\displaystyle }$ ${\displaystyle u}$이(가) 펑하고 가능하면$$ 모든 이웃을 편안하게 하는 데 사용된다.따라서 루프를 반복한 직후 $u{\displaystyle }$ ${\displaystyle u}$은(는) 더 이상 긴장을 풀 수 없으며$$(그리고 더 이상 큐에 있을 필요가 없다.그러나 $x{\displaystyle }$ ${\displaystyle x}$에 의한 이완은 일부 다른 정점들이 이완을 유발할 수 있는 원인이 될 수 있다$$.현재 루프 반복 전에 i [ > d [ + ( , ) ${\displaystyle dist[x]>dist[w]+w(w,x)}$과 같은 정점 x ${\displaystyle w}$이(가) 이미 대기열에 있는$$ 경우현재 루프 반복 중에 이 조건이 충족되면 d ${\displaystyle i}$ ${\displaystyle t}$[ ${\displaystyle x}$ ${\displaystyle ]}$ ${\displaystyle dist[x]}$이(가) 증가하여 불가능하거나 d i ${\displaystyle s}$ $t{\displaystyle }$ [ $]$ ${\displaystyle \{\backslash \mathrm{displaysty}}$ $dist[w]}$이(가) 감소하여 $w{\displaystyle }$ ${\displaysty w}$이(가) 완화되었음을$$ 의미한다.그러나 $w{\displaystyle }$ ${\displaystyle w}$이(가) 완화된 후 아직 없는 경우 대기열에 추가된다.

코롤러리:알고리즘은 더 이상 이완이 불가능할 때만 종료된다.

증명: 더 이상 완화가 불가능할 경우 알고리즘은 대기열에서 정점을 계속 제거하지만, 정점은 성공적인 이완 시에만 추가되기 때문에 더 이상 대기열에 추가되지 않는다.따라서 대기열이 비어 알고리즘이 종료된다.추가 이완이 가능하다면 큐는 비어 있지 않고 알고리즘은 계속 실행된다.

음-가중주기에 소스에서 도달할 수 있는 경우 알고리즘이 종료되지 않는다.음-가중 주기가 존재할 때 완화가 항상 가능하다는 증거를 보려면 여기를 참조하십시오.음의 무게의 사이클이 없는 그래프에서, 더 이상 완화가 불가능할 때, 정확한 최단 경로를 계산했다(증거).따라서 음의 가중치 주기가 없는 그래프에서 알고리즘은 잘못된 최단 경로 길이로 종료되지 않는다.^[5]

러닝타임

알고리즘의 최악의 가동 시간은 표준 Bellman-Ford 알고리즘과 마찬가지로$$$O{\displaystyle }$(${\displaystyle V}$ ${\displaystyle \cdot }$ $){\displaystyle O(V \cdot$ E $)}$이다.^[1]실험 결과 평균 $가동{\displaystyle }$ 시간은 O${\displaystyle }$( ${\displaystyle E}$) ${\displaystyle O(E )}$이며$,$ 실제로 이것은 랜덤 그래프에서는 사실이지만, SPFA가 일반적인 Bellman-Ford 알고리즘처럼 시간$$${\displaystyle }\Omega {\displaystyle \mathrm{}}$ (${\displaystyle V}$ ${\displaystyle {}^{\mathrm{}}}$ )${\displaystyle \Oomega(V ^{2})$로 실행되는 희소성 그래프를 구성할 수 있다.^[6]

최적화 기법

알고리즘의 성능은 후보 정점을 사용하여 다른 정점을 이완시키는 순서에 의해 강하게 결정된다.실제로 $Q{\displaystyle }$ ${\displaystyle Q}$이(가) 우선 순위 대기열이라면 알고리즘은 Dijkstra의 것과 상당히 유사하다.그러나 여기서 우선 순위 대기열을 사용하지 않기 때문에 대기열의 품질을 향상시키기 위해 두 가지 기법을 사용하는 경우가 있는데, 이는 다시 평균 사례 성능(최악의 성능은 아님)을 향상시킨다.두 기법 모두 소스에 가까운 정점이 먼저 처리되도록$$ $Q{\displaystyle }$ ${\displaystyle Q}$의 요소 순서를 재정렬한다.따라서 이러한 기법을 구현할 때 $Q{\displaystyle }$ ${\displaystyle Q}$은(는) 더 이상 선착순 대기열이 아니라 정상적인 이중 연계 목록이나 이중으로 연결된 대기열이$$ 된다.

SLF(Small Label First) 기법.In line 11, instead of always pushing vertex ${\displaystyle v}$ to the end of the queue, we compare ${\displaystyle d(v)}$ to ${\displaystyle d{\big (}{\text{front}}(Q){\big )}}$, and insert ${\displaystyle v}$ to the front of the queue if ${\displaystyle d(v)}$ is smaller. 이 기법의 유사 코드는 ($v{\displaystyle }$ ${\displaystyle v}$을(를) 줄 11의 대기열 끝에 밀어넣은$$ 후):

procedures Small-Label-First(G, Q) if d(백(Q) > d(전면(Q))이면 u := pop back of Q put u를 Q 앞에 밀어 넣는다.

LLL(Large Label Last) 기법.11호선 이후 첫 번째 요소가 평균보다 작도록 큐를 업데이트하고, 평균보다 큰 요소는 큐의 끝으로 이동한다.의사 코드는 다음과 같다.

절차 Large-Label-Last(G, Q) x := 모든 Q의 평균 d(v) > d(전면(Q) > x u := Q의 pop front u := pop front of u를 Q의 뒤로 밀어 넣는다.

참조