Bellman-ford-moore

2022.08.08 - [Track Phase-Turnovering/algorithm 100] - 059 : 타임머신으로 빨리 가기

 

출발 노드에서 다른 모드 노드까지 최단 경로 탐색

- 음수 w가 있어도 수행 가능

- 에지 중심 시행

- 전체 그래프에서 음수 사이클의 존재 여부 판단 가능

 

1

edge list graph and D[index]

- ArrayList<edge> edges > s, e, w

- D[1] = 0, D[2~N] = ∞

 

2

모든 에지를 확인, 정답 배열 업데이트

- if (D[s] != ∞ && D[s] + w < D[e]) >  D[e] = D[s] + w

- 음수 사이클이 없을 때, 두 노드의 최단 거리를 구성할 수 있는 에지의 최대 수는 N-1

 

3

음수 사이클이 존재하는 지 확인

- 모든 에지를 한번씩 다시 사용해, 업데이트되는 노드가 발생하는지 체크

- 업데이트가 되면 음수 사이클이 있다는 뜻으로, 불가함(을 출력)