벨만포드

벨만포드

• 벨만포드란?
  • 그래프에서 최단 경로를 찾는 알고리즘
  • 음의 가중치를 지닌 간선이 있을때도 사용가능
  • 모든 간선을 여러번 검사하여 최단 경로를 찾음
• 알고리즘 단계
  • 초기화 : 모든 정점의 거리를 무한대로 초기화하고, 시작 정점을 0으로 초기화
  • 간선 완화: 모든 간선을 반복하여 검사하면서, 현재 경로보다 더 짧은 경로가 발견되면 거리를 업데이트
  • 반복 : 위의 과정을 모든 정점의 수 -1번 반복
  • 음의 사이클 검사: 추가로 한번 더 모든 간선을 검사하여 거리가 업데이트 된다면, 음의 가중치 사이클이 존재하는 것을 알 수 있음
• 적용 예시
  • 네트워크 라우팅: 음의 비용이 있는 경로를 고려해야하는 경우
  • 게임 개발: 경로 찾기 알고리즘 등