Shortest Path Algorithm: 벨만-포드 알고리즘

 

🧠 개념

• 특정 노드에서 다른 모든 노드까지의 최단 경로를 탐색하는 알고리즘

 

✨ 특징

• 음수 가중치 엣지가 존재하더라도 최단 경로를 구할 수 있음
  • 다익스트라 알고리즘은 모든 가중치가 양수인 경우만 처리 가능
• 그래프 전체에서 음수 사이클의 존재 여부를 판단할 수 있음
• 시간 복잡도 O(VE) → 노드 수 V, 엣지 수 E

 

⚙️ 동작 원리

1. 엣지 리스트로 그래프 구현(엣지 중심으로 동작하는 알고리즘이기 때문) 및 최단 경로 리스트 초기화
2. 모든 엣지를 확인해 최단 경로 리스트 업데이트
   • 최단 경로 리스트를 업데이트하기 위한 반복 횟수는 노드 개수-1
     • 노드 개수가 N이고 음수 사이클이 없을 때 특정 두 노드의 최단 거리를 구성할 수 있는 최대 엣지 개수가 N-1
   • D[s] ≠ ∞ 이고 D[e] > D[s]+w 이면 D[e] = D[s]+w 로 업데이트
     • 시작 노드가 무한대면 계산이 불가능하기 때문에 D[s]가 무한대가 아니어야 한다는 조건 필요
   • 업데이트 반복 횟수가 K번이면 해당 시점에서 최단 경로 리스트의 값은 '시작점에서 K개의 엣지를 사용해서 각 노드에 갔을 경우의 최단 거리'를 의미함
3. 음수 사이클 존재 여부 확인
   • 2번 단계에서 만들어진 최종 리스트는 음수 사이클이 없는 경우임
   • 음수 사이클의 존재 여부를 확인하기 위해 모든 엣지를 한 번씩 다시 사용
   • N개의 엣지를 사용했을 때 업데이트가 발생하면 음수 사이클이 있다는 뜻이 됨
     • N-1개의 엣지를 썼을 때보다 더 짧은 거리가 나오려면 음수 사이클을 도는 방법 밖에 없음
   • 음수 사이클의 의미
     • 음수 사이클을 무한히 돌면 가중치 값이 계속 감소하기 때문에 최단 거리를 구할 수 없음(최단 거리를 구하는 것이 무의미함)

 

🤓 그림 예시

1. 동작 원리 1단계 예시 그림

(리스트 밑에 그림 넣으면 번호가 끊긴다는 걸 오늘 처음 안 사람)

 

💻 구현

일단 파이썬으로 열심히 구현해보는 중이라 다 되면 추가해야지 ~

 

©️ 출처

• YouTube '알고리즘 코딩테스트 핵심이론 강의 - 벨만포드'