벨먼-포드 알고리듬

게시 2023/12/19 업데이트 2024/08/29

By Mascari4615

8 분읽는 시간

벨먼-포드 알고리듬

단일 시작점 최단경로
벨먼-포드 알고리듬

음의 사이클
A -( 1 )→ B -( 2 )→ C -( -3 )→
돌떄마다 가중치가 무한히 작아짐

💫 Bellman-Ford Algorithm

포드이 먼저 만들었지만, 이를 개선한 벨먼이 더 네임드여서.
포드 알고리듬이라고도 부름

원칙은 2차원인데, 뒤에 공부하다보면 1차원으로도 충분해짐 (i가 사라짐) 그래서 D_{i_{(d) 처럼 아래첨자로 i르 둠}}

PPT 사진

식 의미
모든 간선들 중, k에서 d로 가는 간선들 중, 가장 짧은 놈을 대상으로..

d가 10이라 치고, d와 이어진 정점이 2 3 6이라고 하면, k는 2, 3, 6이고 이중에서 가장 가중치가 짧은 놈이 대상

min[D_{i-1_{(d) 는 없어도 되는데
왜Why, 일단 더 길어질 수는 없어, 최적이었으닌까
적어지면 최단 경로가 짧아진다 근데 이게 변하지 않을 수 있다!! = 기존 값을 유지할 수 있다!! 를 의미하기 위해 둔 것, 없어도 의미는 같음}}

다익스트라 알고리듬에서 보았던 정의와 매우 유사(실제로 같은 정의, distance 배열 썻던것처럼) 각 간선 <k, d>를 n-1번 완화(relaxation: 더 나은 경로로 변경, 더 나은 경로를 찾는 것)

~번 완화 한다

@ TODO: 왜 e 지수..?

2차원 배열 x = 정점 y = 각 시행 (i-1, i, i+1, …) x, y = 거리

(1,5) 4
(5,7) 6

i-1 1=10 5=20 7=40 i 1=8 5=14 7=26 i+1 i= 5=12 7=20

어차피 값이 바뀌었으면 다음 시행 때 값이 갱신되는 것이 자명 (변경이 짧아지는 경우 밖에 없으니까)

그러면 계산할때 그냥 새로 갱신된 값을 기준으로 바로 계산 하자
→ 변경되는 값을 기존거에 덮어쓰기 하자 → 1차원 배열만 잇어도 된다

n-1 만큼 루프를 돌리고, 한 번 더 기준 연산을 하는데, 또 줄어들면 그건 음의 사이클이다.

A -(1)→ B -(1)→ C -(1)→ D -(1)→ E
A를 시작점으로 할 때

ㄱ) (D, E), (C, D), (B, C), (A, B)
ㄴ) (A, B), (B, C), (C, D), (D, E)

ㄱ은 마지막 반복까지 가서야 최단 경로가 결정
ㄴ은 첫 반복 (한 번의 반복) 으로 최단경로가 결정

따라서 배열에 더 변화가 없으면, 반복을 멈추고 알고리듬의 실행을 종료
세타(ne) → O(ne)

앞 단계와 현 단계에서 D[u]가 변경된 간선 (u, v)만 살펴본다.
완화 횟수를 줄일 수 있다.