최단 경로 - 벨만 포드 Bellman Ford

벨만 포드 Bellman Ford

: 그래프에서 최단경로를 구하는 알고리즘으로 시간복잡도는 O(VE)이다.

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

다익스트라와의 차이점

• 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있기 때문에 음수 가중치 에지가 있어도 수행할 수 있음
• 대신 시간 복잡도가 늘어남
  (다익스트라는 그리디, 벨만포드는 모든 경우의 수를 고려하는 동적 계획법)

구현

에지 리스트, 최단 경로 배열

1. 에지 리스트로 그래프를 구현하기(리스트의 값에 (출발노드, 도착노드, 가중치) 이렇게 들어가도록)
2. 최단 경로 배열 초기화하기
3. 모든 에지를 확인해 최단 경로 배열 업데이트하기
   (업데이트 반복 횟수는 노드 개수 - 1, 노드 개수와 같아지는 순간 사이클이 생김)