최단 경로 고속 알고리즘

최단 경로 고속 알고리즘(SPFA)은 가중 방향 그래프에서 단일 소스 최단 경로를 계산하는 Bellman-Ford 알고리즘의 개선입니다.이 알고리즘은 무작위 희소 그래프에서 잘 작동하며 음의 가중치 ^[1]에지를 포함하는 그래프에 특히 적합합니다.그러나 SPFA의 최악의 경우 복잡성은 Bellman-Ford의 복잡성과 동일하므로 음이 아닌 에지 가중치가 있는 그래프의 경우 Dijkstra 알고리즘이 선호됩니다.SPFA 알고리즘은 에드워드 F에 의해 처음 발표되었습니다. 1959년 무어는 너비 우선 ^[2]탐색의 일반화로서 SPFA는 무어의 "알고리즘 D"입니다.^[3] 1994년에 이 알고리즘을 재발견한 중국 연구자 판딩 an에 의해 "최단 경로 고속 알고리즘(SPFA)"이라는 이름이 주어졌습니다.

알고리즘.

가중 방향 $G=(V,E)$ G $=$ ( $G=(V,E)$ ) {\ $displaystyle$ G=( $V, E)}$ 및 $G=(V,E)$ 소스 $정점$ {\ $displaystyle$ 이 주어지면 SPFA 알고리듬은 그래프에서s{ $displaystyle$ 에서 각 정점 ${displaystyle$ v $v$ 까지의 $최단$ 경로를 찾습니다.s ${displaystyle}$ 에서 $s$ v ${displaystyle$ v}까지의 $v$ 최단 경로 길이는 각 $정점$ v ${displaystyle$ v $v$ 에 대해 d $)$ { $displaystyle$ d $(v)}$ 에 $d(v)$ 저장됩니다.

SPFA의 기본 아이디어는 각 정점이 인접한 정점을 완화하기 위한 후보로 사용된다는 점에서 Bellman-Ford 알고리듬과 동일합니다.후자보다 향상된 점은 SPFA가 모든 정점을 맹목적으로 시도하는 대신 후보 정점의 대기열을 유지하고 정점이 완화된 경우에만 대기열에 정점을 추가한다는 것입니다.이 프로세스는 더 이상 정점을 완화할 수 없을 때까지 반복됩니다.

아래는 ^[4]알고리즘의 유사 코드입니다. $Q$ 서 Q ${displaystyle$ Q $}$ 는 $Q$ 후보 정점의 선입선출 대기열이고 $w(u,v)$ $w(u,v)$ ( $){displaystyle$ w $(u, v$ )}는 $w(u,v)$ ( $,$ ){ $displaystyle (u, v$ 의 $(u,v)$ 에지 가중치입니다.

유클리드 거리를 기반으로 한 SPFA의 데모입니다.빨간색 선은 (지금까지 관찰된) 가장 짧은 경로 피복입니다.파란색 선은 이완이 발생하는 위치를 나타냅니다. 즉, 소스에서 v

{displaystyle

v

v

로

v

가는 경로를 제공하는 Q

{displaystyle

Q

Q

의

노드

u{

displaystyle

u}와

u

v

합니다.

프로시저 V(G) 2 d(v) := ∞ 3 d(s) := Q가 비어 있지 않은 동안 E(G)의 각 에지(u, v)에 대한 Q 7에 대해 Q 5에 푸시하는 각 정점에 대한 Shortest-Path-Faster-Algorithm(G, s) 1(G, s) 1(d) + w(v) <d(v) d(d) 9(d) +(d(d) +(d) +(d) +(d) +(d) +(d(d) +(d) +(d) +(d) +(d)10 v가 Q에 없으면 11이 v를 Q에 밀어 넣습니다.

이 알고리즘은 또한 각 방향이 없는 에지를 반대 방향의 두 방향 에지로 대체하여 방향이 없는 그래프에 적용할 수 있습니다.

정확성 증명

우리는 알고리즘이 잘못된 최단 경로 길이를 계산하지 않는다는 것을 증명할 것입니다.

Lemma: 대기열이 비어 있는지 확인할 때마다 현재 완화를 유발할 수 있는 정점이 대기열에 있습니다.

증명: 조건을 확인할 때 두

정점

u{

displaystyle

u

u

} 및

{displaystyle

w

}

에

dist[w]>dist[u]+w(u,w)

w

대해

dist[w]>dist[u]+w(u,w)

[

w

>

dist[w]>dist[u]+w(u,w)

[u]

+

w(u,

인

dist[w]>dist[u]+w(u,w)

u

{displaystyle

u}가

u

대기열에

있음

을 보여줍니다.우리는 이미 발생한 루프의 반복 횟수를 유도하여 그렇게 합니다.먼저 루프가 입력되기 전에 이것이 확실히 유지된다는 점에 주목합니다.

u\not =s

가

u\not =s

{\

displaystyle u

\not

u\not =s

u=s

s

}

이면 이완이 불가능합니다. u

=

{\

displaystyle

u=

s}

에서 이완이 가능하며, 루프가 입력되기 직전 대기열에 추가됩니다.자, 루프 안에서 무슨 일이 일어나는지 생각해 보세요.

정점

u{

displaystyle

u}는

u

팝업되며, 가능하면 모든 인접 관계를 완화하는 데 사용됩니다.따라서 루프가

u

된 직후 u

{displaystyleu}

는

u

더 이상 이완을 발생시킬 수 없습니다(더 이상 대기열에 있을 필요가 없습니다).그러나 x

{displaystyle

x

}

에

x

의한

이완으로 인해 일부 다른 정점이 이완을 일으킬 수 있습니다.현재 루프 반복 전에

dist[x]>dist[w]+w(w,x)

[

dist[x]>dist[w]+w(w,x)

] >

dist[x]>dist[w]+w(w,x)

[

dist[x]>dist[w]+w(w,x)

] +

dist[x]>dist[w]+w(w,x)

(

dist[x]>dist[w]+w(w,x)

) {{

displaystyle

dist[

x]> dist[w]

+

w(w, x

)}와

dist[x]>dist[w]+w(w,x)

같은

정점

x {\

displaystyle

w

}

이

x

(가) 있으면 w

{displaystyle

w}가

w

이미 대기열에

있습니다

.이 조건이 현재 루프 반복 중에 참이 되면 불가능한

dist[x]

[

]{displaystyle

dist

[

x]

가

dist[x]

dist[w]

하거나

displaystyle

dist[

w]

가 감소하여

dist[w]

w

{displaystyle

w

}

가

w

완화되었음을

w

합니다.그러나 w

{displaystyle

w

}

이

w

(가)

w

된 후 대기열이 아직 없는 경우 대기열에 추가됩니다.

결과:알고리즘은 더 이상의 이완이 불가능한 경우에만 종료됩니다.

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

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

러닝타임

실험에 따르면 랜덤 그래프에서 평균 실행 시간은 O $)$ {\ $displaystyle O$ ( $\Omega (|V|\cdot |E|)$ 이지만 $O(|E|)$ , 알고리즘의 최악의 경우 실행 시간은 Bellman-Ford ^[1]^[6]알고리즘과 동일한 $Δ($ V Δ E) \Displaystyle \Omega( $V \cdot$ E $\Omega (|V|\cdot |E|)$ 입니다.

최적화 기법

알고리즘의 성능은 후보 정점이 다른 정점을 완화하는 데 사용되는 순서에 따라 강하게 결정됩니다.실제로 Q ${displaystyle$ Q $}$ 가 $Q$ 우선순위 $큐라면$ 알고리즘은 Dijkstra의 알고리즘과 매우 유사합니다.그러나 여기서 우선 순위 대기열이 사용되지 않기 때문에 대기열의 품질을 향상시키기 위해 두 가지 기술이 사용되기도 하며, 이는 결과적으로 평균적인 경우 성능을 향상시킵니다(최악의 경우 성능은 향상시키지 않습니다).두 기법 모두 소스에 더 가까운 정점이 먼저 처리되도록 Q ${displaystyle$ Q $}$ 의 $Q$ 요소 순서를 재정렬합니다.따라서 이러한 기술을 구현할 때 ${displaystyle$ Q $}$ 는 $Q$ 더 이상 선입선출 큐가 아니라 일반적인 이중 링크 목록 또는 이중 종단 큐입니다.

소형 라벨 우선(SLF) 기법.11행에서는 $꼭짓점$ v{ $displaystyle$ v $}$ 를 $v$ 항상 대기열 끝으로 밀어 넣는 대신 ( $)$ { $displaystyle$ d $($ $v)}$ 를 $d(v)$ d(앞 $)$ {\ $text{front}}(Q)$ {\ $big}}$ 과 $d{\big (}{\text{front}}(Q){\big )}$ 와) $d(v)$ 했습니다 $d(v)$ d $)$ {\ $displaystyle$ d $(v)}$ 이 $d(v)$ (가) 작을 $d(v)$ 대기열 앞에 v{\ $displaystyle$ v $}$ 를 $v$ $v$ 합니다.이 기법에 대한 유사 코드는 ( $11행$ 의 큐 끝에v{ $displaystyle$ v $}$ 를 $v$ $누른$ 후):

프로시저 Small-Label-First(G, Q) if d(back(Q)) < d(front(Q)) 그 다음 u := pop back of Q의 push u를 Q 앞으로 밀어넣습니다.

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

프로시저 Large-Label-Last(G, Q) x := 모든 vin Q에 대한 d(v)의 평균 d(front(Q)) > x u : = Q의 pop front에서 Q의 뒤로 푸시업합니다.

레퍼런스

^ ^a ^b 이른바 SPFA 알고리즘 정보
^ Moore, Edward F. (1959). "The shortest path through a maze". Proceedings of the International Symposium on the Theory of Switching. Harvard University Press. pp. 285–292.
^ Duan, Fanding (1994), "关于最短路径的SPFA快速算法 [About the SPFA algorithm]", Journal of Southwest Jiaotong University, 29 (2): 207–212
^ "Algorithm Gym :: Graph Algorithms".
^ "Shortest Path Faster Algorithm". wcipeg.
^ "Worst test case for SPFA". Retrieved 2023-05-14.

[poj-1] 이른바 SPFA 알고리즘 정보

[2] Moore, Edward F. (1959). "The shortest path through a maze". Proceedings of the International Symposium on the Theory of Switching. Harvard University Press. pp. 285–292.

[duan-3] Duan, Fanding (1994), "关于最短路径的SPFA快速算法 [About the SPFA algorithm]", Journal of Southwest Jiaotong University, 29 (2): 207–212

[codeforce-4] "Algorithm Gym :: Graph Algorithms".

[5] "Shortest Path Faster Algorithm". wcipeg.

[6] "Worst test case for SPFA". Retrieved 2023-05-14.

[1]

[2]

[3]

[4]

[5]

[6]

v t 그래프 및 트리 트래버설 알고리즘
α-β 가지치기 A* IDA* LPA* SMA* 최선 우선 검색 보 검색 양방향 검색 폭 우선 검색 사전 편찬 병렬 B* 깊이 우선 검색 반복 심화 D* 프린지 검색 점프 포인트 검색 몬테카를로 나무 찾기 SSS*
최단 경로	벨먼-포드 데이크스트라의 플로이드-워셜 존슨의 최단 경로 더 빠른 속도 옌스
최소 신장 트리	보르ů브카 크루스칼 프림스 역삭제
그래프 검색 알고리즘 목록

Search