존슨 알고리즘

존슨 알고리즘

클래스	최단 경로 문제를 모두 해결(가중 그래프)
데이터 구조	그래프
최악의 경우 공연	${\displaystyle O(V ^{2}\log V + V E )}$

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

Johnson의 알고리즘은 에지 가중치 방향 그래프에서 모든 꼭지점 쌍 사이의 최단 경로를 찾는 방법이다.이것은 가장자리 무게의 일부가 음수가 되도록 허용하지만 음의 무게 주기는 존재하지 않을 수 있다.Bellman-Ford 알고리즘을 사용하여 모든 음의 가중치를 제거하는 입력 그래프의 변환을 계산하여 변환 그래프에 Dijkstra 알고리즘을 사용할 수 있도록 한다.^[1][2]그것은 도날드 B의 이름을 따서 지어졌다. 1977년에 이 기술을 처음 출판한 존슨.^[3]

유사한 재가중 기법은 음이 아닌 에지 가중치를 가진 그래프에서 동일한 두 꼭지점 사이의 최소 총 길이의 두 개의 분리 경로를 찾기 위해 Suurballe의 알고리즘에서도 사용된다.^[4]

알고리즘 설명

Johnson의 알고리즘은 다음과 같은 단계로 구성된다.^[1][2]

1. 먼저 그래프에 새로운 노드 q가 추가되고, 각 노드에 제로 웨지 에지로 연결된다.
2. 둘째, Bellman-Ford 알고리즘은 새로운 정점 q부터 시작하여 q에서 v까지의 경로의 최소 중량 h(v)를 찾기 위해 사용된다. 이 단계가 음의 사이클을 감지하면 알고리즘이 종료된다.
3. 다음으로 원본 그래프의 가장자리는 Bellman-Ford 알고리즘에 의해 계산된 값을 사용하여 재가중치된다. ${\displaystyle u}$에서 v까지의 가장자리로 w${\displaystyle (}u{\displaystyle }$,${\displaystyle }$v )$${\$displaystyle$ w$(u,v)}$이$($가) 새로운 길이 w(u,v) + h(v)가 주어진다.
4. 마지막으로, q가 제거되고, Dijkstra의 알고리즘은 재가중 그래프에서 각 노드 s에서 다른 모든 꼭지점까지의 최단 경로를 찾는 데 사용된다.그런 다음 원래 그래프의 거리는 Dijkstra 알고리즘에 의해 반환되는 거리에 h(v) - h(u)를 추가하여 각 거리 D(u , v)에 대해 계산된다.

예

존슨 알고리즘의 처음 3단계는 아래 그림에 묘사되어 있다.

그림 왼쪽의 그래프는 두 개의 음 에지가 있지만 음의 사이클은 없다.중심 그래프는 새로운 꼭지점 q, 시작 꼭지점으로 q를 가진 Bellman-Ford 알고리즘에 의해 계산된 최단 경로 트리 및 q에서 해당 노드까지의 최단 경로 길이로서 서로 다른 노드에서 계산된 값 h(v)를 나타낸다.q는 각 정점에 길이 0의 가장자리를 가지며 최단 경로는 더 이상 해당 가장자리보다 클 수 없기 때문에 이 값들은 모두 양성이 아니라는 점에 유의하십시오.오른쪽에는 각 에지 중량 $w{\displaystyle (u}$, v${\displaystyle }$) ${\displaystyle$ w(u$,v)}$을 w(u,v) + h(u) - h(v)로$$ 교체하여 형성된 재가중 그래프가 표시된다.이 재가중 그래프에서 모든 에지 가중치는 음수가 아니지만, 두 노드 사이의 최단 경로는 원래 그래프에서 동일한 두 노드 사이의 최단 경로와 동일한 에지 시퀀스를 사용한다.알고리즘은 재가중 그래프의 네 개의 시작 노드에 각각 Dijkstra의 알고리즘을 적용하여 결론을 내린다.

정확성

재가중 그래프에서, 한 쌍의 노드와 t 사이의 모든 경로는 동일한 양의 h(s) - h(t)가 추가된다.이전의 진술은 다음과 같이 증명할 수 있다.p를 $s{\displaystyle }$ -${\displaystyle t}$ ${\displaystyle s-t}$ 경로로$$ 설정하십시오.재가중 그래프에서 가중치 W는 다음 식에 의해 주어진다.

${\displaystyle {\bigl (}w,p_{1})+h-h(p_{1}{1}{\bigr )}+{\bigl (}w(p_{1},p_{2})+h(p_{1})+h(p_{2}){\bigr )}++...+{\bigl (}w(p_{n},t)+h(p_{n}-h(t){\bigr )}.}$

매${\displaystyle }$+ ${\displaystyle h}$( ${\displaystyle p_{}}$ i${\displaystyle {}_{}}$) ${\displaystyle +h(p_{i}}}$은(는) 이전 브라켓 식에서${\displaystyle }$- ${\displaystyle h}$( p ${\displaystyle i_{}}$) ${\displaystyle -h(p_{i}})$에 의해 취소되므로$$ W에 대해 다음 식이 남게 된다.

${\displaystyle {\bigl (}w(s,p_{1})+w(p_{1},p_{2}+)+...+w(p_{n},t){\bigr )}+h(s)-h(t)}$

고사리 표현은 원래 가중치에서 p의 무게다.

재가중치는 모든 $s{\displaystyle }$- ${\displaystyle t}$ ${\displaystyle s-t}$ 경로의$$ 중량에 동일한 양을 추가하므로 재가중 후 최단 경로인 경우에만 원래 가중치에서 경로가 최단 경로다.q에서 어떤 노드로의 최단 경로에 속하는 가장자리의 중량은 0이며, 따라서 재가중 그래프에서 q에서 모든 노드에 이르는 최단 경로의 길이는 0이 되지만, 여전히 최단 경로로 남아 있다.따라서 음의 가장자리는 있을 수 없다: 만약 edge uv가 재가중 후 음의 무게를 가졌을 경우, q에서 u까지의 영의 길이 경로가 이 가장자리와 함께 q에서 v까지의 음의 길이 경로를 형성할 것이며, 이는 모든 정점의 거리가 q에서 0이라는 사실과 모순된다.음의 가장자리가 존재하지 않는 것은 Dijkstra 알고리즘에 의해 발견된 경로의 최적성을 보장한다.원래 그래프의 거리는 재가중 변환을 역방향으로 하여 재가중 그래프에서 Dijkstra 알고리즘에 의해 계산된 거리에서 계산할 수 있다.^[1]

분석

The time complexity of this algorithm, using Fibonacci heaps in the implementation of Dijkstra's algorithm, is ${\displaystyle O( V ^{2}\log V + V E )}$: the algorithm uses ${\displaystyle O( V E )}$ time for the Bellman–Ford stage of the algorithm,${\displaystyle 및}$ $O{\displaystyle (V}$ ${\displaystyle \log }$ ${\displaystyle }$ ${\displaystyle V}$+ ${\displaystyle E}$) ${\displaystyle O(V$${\displaystyle }$$\log V$+ E$)}$ Dijkstra 알고리즘의 각 V {\$displaystyle$V$}$ 인스턴스화에$$ 대해$$.따라서 그래프가 희박할 때는 총 시간이 Floyd-Warshall 알고리즘보다 빠를 수 있는데, 이 알고리즘은 시간 $O{\displaystyle }$(${\displaystyle V}$ $){\displaystyle O(V ^{3})$에서 동일한 문제를 해결할 수 있다$.$^[1]

참조

외부 링크

• 부스트: 모든 쌍의 최단 경로