86 lines
4.3 KiB
Markdown
86 lines
4.3 KiB
Markdown
deck:: Logseq/coding tip
|
|
|
|
- ## 1. 개념(Concept)
|
|
- 그래프의 특정 시작 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘.
|
|
- [[다익스트라 알고리즘 (Dijkstra Algorithm)]] 와의 차이점
|
|
- {{cloze 음의 가중치}}가 있는 간선을 처리 할 수 있다.
|
|
id:: 6953c01a-2e75-4d9c-a2df-9392f4270f37
|
|
- {{cloze 음수 사이클}}의 존재 여부를 탐지 할 수 있다.
|
|
extra:: 음수 사이클(Negative Cycle)이란, 간선 가중치의 합이 음수가 되는 순환경로를 의미하고 이 사이클을 계속 순환하면 총 거리가 음의 무한대로 발산하기 때문에 최단 거리를 정의 할 수 없게 된다.
|
|
id:: 6953c026-75f3-4fb4-babe-71ef726abdd9
|
|
-
|
|
- ## 2. 동작 원리 (Algorithm Flow)
|
|
- ### 핵심 아이디어 :-> 모든 간선을 $V-1$번 반복해서 확인한다.
|
|
extra:: 최단 경로는 최대 V-1개의 간선을 가질 수 있기 때문.
|
|
id:: 6953c0e9-4e24-4508-81c3-9f404f9d423b
|
|
- 1) 초기화 : 시작 정점의 거리는 0, 나머지 모든 정점의 거리는 무한대로 설정한다.
|
|
#+BEGIN_EXTRA
|
|
```python
|
|
INF = sys.maxsize # float("inf")
|
|
dist = [INF] * (v + 1)
|
|
dist[start_node] = 0
|
|
```
|
|
#+END_EXTRA
|
|
- 2) V-1회 반복
|
|
- 그래프의 모든 간선을 하나씩 확인한다.(시작점(u), 도착점(v), 가중치(w))
|
|
- 확인하면서 특정 조건이 되면 갱신한다.
|
|
id:: 6953c838-515c-4773-a0f0-2df4a6746ccc
|
|
(이때의 갱신 조건과 파이썬 코드를 답하면?) #card
|
|
- 이때 dist[u]의 값이 무한대가 아니고 dist[v]의 값이 dist[u]+w 보다 크다면 dist[v]를 갱신한다.
|
|
- ```python
|
|
for i in range(V): # 원래 V-1번만 반복해야하지만 음수 사이클 판별을 위해 보통 V까지 함.
|
|
for u, v, w in edges:
|
|
if dist[u] != INF and dist[u] + w < dist[v]:
|
|
dist[v] = dist[u] + w
|
|
```
|
|
- 3) 음수 사이클 판별
|
|
- V-1회 반복한 뒤 한번 더(V번째) 확인한다.
|
|
id:: 6953c8e8-c7e6-4083-852e-6838e99963cd
|
|
이때에도 갱신되는 값이 있다면 음수 사이클이 존재(가중치 합이 무한히 작아질 수 있다는 뜻)함을 의미한다.
|
|
파이썬 코드로 작성하면 다음과 같다. #card
|
|
- ```python
|
|
for i in range(V) :
|
|
for u, v, w in edges:
|
|
if dist[u] != INF and dist[u] + w < dist[v]:
|
|
dist[v] = dist[u] + w
|
|
|
|
# V번째 반복인데도 갱신이 일어났다면 음수 사이클이 존재한다는 것!
|
|
if i == V - 1 :
|
|
return True
|
|
|
|
return False
|
|
```
|
|
-
|
|
- ## 3. 코드 (python)
|
|
- ```python
|
|
import sys
|
|
|
|
INF = sys.maxsize
|
|
|
|
def bellman_ford(start, V, edges) :
|
|
dist = [INF] * (V+1)
|
|
dist[start] = 0
|
|
|
|
for i in range(V) :
|
|
for u, v, w in edges :
|
|
if dist[u] != INF and dist[u] + w < dist[v] :
|
|
dist[v] = dist[u] + w
|
|
|
|
if i == V - 1 :
|
|
return True
|
|
|
|
return False
|
|
```
|
|
-
|
|
- ## 4. 시간복잡도
|
|
- {{cloze $O(VE)$}}
|
|
extra:: E : 간선 갯수, V : 정점 갯수
|
|
id:: 6953c0cd-c4e5-4773-b010-d6e85614e4b1
|
|
-
|
|
- ## 5. 알고리즘 응용(슈퍼소스)
|
|
- 만약 특정 시작 지점에서 도달 가능한 지점 까지의 최단거리를 구하는게 목적이 아닌 음의 사이클 존재 여부만을 확인하고 싶다면? #card
|
|
id:: 6953cbbd-2d8c-4351-bfc8-98f79fc347a1
|
|
- dist 배열을 처음부터 전부 0으로 초기화 한 뒤 벨만포드 알고리즘을 돌린다. 이때 V번째 반복에서 갱신이 일어나면 사이클이 발생하는 것이다.
|
|
- 슈퍼소스란 ? 가상의 시작점으로서 모든 노드와 연결되어 있으면서 그 가중치가 0인 시작점을 의미한다.
|
|
- 즉 임의로 간선들의 배열에 가상의 점을 추가하고 그와 연결되는 가중치 0의 간선들을 추가해서 벨만포드 알고리즘을 돌려도 되고, 위에서 말한 것 같이, 처음부터 모든 거리 배열을 0으로 만들어서 돌려도 된다.
|
|
- 모든 거리 배열을 0으로 만든다는 것은 임의의 시작점에서 이미 모든 노드로 가중치가 0인 상태로 연결되어서 한번 갱신 되었다고 볼 수 있기 때문. |