[SSP] 벨만 포드 알고리즘

목적:  방향 그래프, 음의 가중치를 갖는 그래프에서 SSP를 찾는 것

DP 스타일.

 

- 모든 SP는 negative cycle 이 없을 때만 수행 가능

- 벨만 포드는, 다익스트라와 달리, 그래프 내에 negative edge가 있더라도 실행 가능 (심지어 negative cycle의 유무를 detect)

 

- |V|-1까지 단계를 진행했을 때 'single source로부터 그래프 내 모든 node의 최단거리'가 확정됨! (|V| = G 내 노드 개수)

- 정점의 개수만큼 모든 간선을 Relax

---

Why |V|-1?

source 제외한 각 노드 (총 |V|-1 개)에 대해, 그래프 내 모든 edge에 대한 연산 수행해야 함.

연산량 무려 O(|V||E|)

결국 정해진 source에 대한 특정 노드까지의 최단거리를 구해야 하는데, 해당 최단 거리는 더 작은 최단 거리들의 합으로 구성되어 있음.

source로부터 가장 멀리 떨어진 노드 간 연결하는 edge 개수는, 최대 |V|-1 이고, 각각은 최단거리들의 합임 (마치 optimal substructure). 따라서 

 

https://ssungkang.tistory.com/entry/Algorithm-%EB%B2%A8%EB%A7%8C%ED%8F%AC%EB%93%9CBellman-Ford-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

https://ssungkang.tistory.com/entry/Algorithm-%EB%B2%A8%EB%A7%8C%ED%8F%AC%EB%93%9CBellman-Ford-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

 

=> 최악의 경우일 때, 순환을 포함해서는 안되므로(negative cycle은 불가능, non-negative cycle은 최단 경로로 포함될 수 없음) 최대 V개의 정점을 가지고, 그 때의 간선의 개수가 V-1기 때문

---

Relax?

- δ(s,v) : source -> v까지 실제 최단경로 비용

- d[v] : source -> v까지 추정 최단경로 비용 (그래프 노드 안에 적힌 값으로 표현, node.d)

Relaxation:  d[v]가 δ(s,v)의 상한이 되도록 유지하고 조정하는 함수, 궁극적으로는 d[v]가 δ(s,v)까지 줄어들도록 조정함

 

https://victorydntmd.tistory.com/103

v까지 최단거리 발견하면 그걸로 다시 업데이트! 또 업데이트!!! 반복쓰 ~.

---

벨만포드 전체 알고리즘 !

 

- Bellman-Ford 알고리즘은 정점의 개수만큼 모든 간선을 Relax하기 때문에 엄청난 연산

- 덕분에 음의 가중치가 있는 그래프의 단일 출발지 최단경로를 구할 수 있고, 그래프가 음의 순환구조를 갖는다면 이를 식별할 수 있음

 

구체적인 예시:

https://victorydntmd.tistory.com/104

[알고리즘] SSP(2) - 벨만 포드 알고리즘 ( Bellman-Ford Algorithm )

---

Time-Analysis?

line 1 : theta(|V|)

그래프를 초기화

d[s] = 0, d[v] = infinite

 

line 2 ~ 4 : O((|V|-1)*(|E|)) = O(|V||E|)

정점의 개수만큼 반복문을 돌면서, 모든 간선에 대해 Relax를 수행

 

line 5 ~ 8: theta(|E|)

음의 가중치를 갖는 순환경로가 존재하는지 확인

존재한다면 false를 반환하고, 존재하지 않으면 벨만 포드 알고리즘이 잘 작동했다는 true를 반환

 

출처: https://victorydntmd.tistory.com/104

---

https://jeonyeohun.tistory.com/96

[알고리즘 정리] 최단경로(Shortest Path)