벨만 포드 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘입니다.

(주요 특징)

• 기능 : 특정 출발 노드에서 다른 모든 노드까지의 최단 경로 탐색
• 특징 :
  • 음수 가중치 엣지가 있어도 수행이 가능하다
  • 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있다.
  • DP - 모든 경로 가능성을 차근차근 비교하는 동적 프로그래밍으로, 시간이 오래 걸리지만 음수도 안전하게 처리할 수 있다.

Q) 벨만 포드랑 다이젝스트라 모두 최단 경로일때 쓰는거잖아. 그럼 차이점은?

일단 다이젝트스라로 접근하되, 음수 가중치, 음수 사이클을 탐지해야 할 때, 벨만 포드를 의심하자. 왜냐면 속도 자체가 벨만 포드가 좀 더 느리다.

다이젝스트라 - greedy (매 순간 지금까지 제일 가까운 곳만 가)

벨만포드-dp (완화반복)

[ bellman-ford 알고리즘 구현 방법]