🌓 벨먼-포드 알고리듬

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

• 문제의 이해: 단일 시작점 최단 경로를 찾는 알고리듬
  • 출발 지점으로부터 나머지 다른 모든 지점까지의 최단 경로를 찾는 문제
  • 음의 사이클(negative cycle)이 없어야 최단 경로를 찾을 수 있음 (실제 문제에서 음의 사이클이 있는지없는지 여부는 확신할 수 없음, 그래서 벨먼포드가 좋음, 여부를 확실히 몰라도 예방이 되니까)
  • 종류
    • 다익스트라 알고리듬
      • 욕심쟁이 방법을 사용하기 때문에 빠름
      • 그래프의 간선 가중치가 음수가 아니라고 가정 (범용성이 떨어짐)
    • 벨먼-포드 알고리듬(Bellman-Ford algorithm)
      • 동적 계획법을 사용
      • 음수의 간선 가중치를 갖는 그래프에 대해서도 정확하게 동작
      • 출발점에서 도달할 수 있는 음의 사이클이 존재하지 않는 한 정확한 최단 경로를 구하며 음의 사이클이 있다면 그 존재를 알려줌
• 무작위 기법: 2장 참조, n!
• 최적 부분구조: 2장 참조

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

💫 Bellman-Ford Algorithm

---

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

• 문제의 순환적 정의
  • 최종 목표: 시작 정점에서 각 정점으로의 최단 경로
  • 최우선 목표: 시작 정점에서 각 정점으로의 최단 경로의 길이
    • V ={1, …, n}, E가 주어졌을 때 출발점에서 정점 d까지 최단경로는 최대 n-1개 간선을 거침
    • 출발점에서 최대 n-1개 간선을 거쳐 정점 d에 도달하는 최단 경로의 길이는 다음 중 최소값
      • • 출발점에서 최대 n-2개 간선을 거쳐 정점 1에 도달하는 최단 경로 길이+<1,d> 가중치
      • • 출발점에서 최대 n-2개 간선을 거쳐 정점 2에 도달하는 최단 경로 길이+<2,d> 가중치
      • • …
      • • 출발점에서 최대 n-2개 간선을 거쳐 정점 n에 도달하는 최단 경로 길이+<n,d> 가중치
      • d도 1~n이라 중복되는 경우 (갔던 곳 또 가는 경우)가 있을 수잇음
    • 수학적 귀납법
      • 귀납 조항: 출발점에서 각 정점까지 최대 i-1개의 간선을 거치는 최단 경로를 안다면 출발점에서 각 정점까지 최대 i개의 간선을 거치는 최단 경로를 구할 수 있음
      • 기본 조항: 출발점에 대한 최단 경로는 0이고 나머지 정점들에 대한 최단 경로는 ∞
  • 출발점 s에서 최대 i개의 간선을 거쳐 정점 d에 도달하는 최단 경로의 길이를 D_i(d)라 하고 간선 <v₁, v₂>의 가중치를 w(v₁, v₂)라 하면

원칙은 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)

Moore의 SPFA (Shortest Path Faster Algorithm)

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