벨만-포드

벨만-포드(Bellman-Ford) ?

• 벨만포드 알고리즘은 그래프에서의 단일 출발지 최단 경로 문제(One-To-All)를 해결하기 위한 알고리즘으로, 다익스트라 알고리즘과 달리 **음수 가중치 간선**이 포함된 그래프에서도 사용할 수 있다.

<aside> 💡

경로 탐색 방식에는 3가지가 있다 ?

• One-To-One: 한 지점에서 다른 특정 지점까지의 최단 경로 구하기

• One-To-All: 한 지점에서 다른 모든 지점까지의 최단 경로 구하기

• All-To-All: 모든 지점에서 다른 모든 지점까지의 최단 경로 구하기 </aside>

• 다만, 음수 사이클이 있는 경우에는 최단 경로를 계산할 수 없으며, 이를 탐지하는 기능도 포함되어 있다.

💡 핵심 개념 - 단계별 Relaxation

• 각 간선을 반복적으로 확인하며, 시작 정점에서 다른 정점까지의 최소 비용을 점진적으로 업데이트한다.
• 한 정점에서 다른 정점으로 이동하는 최소 비용은 최대 V(정점 개수)-1번만큼의 반복으로 구할 수 있다.

💡 핵심 개념 - 음수 사이클 탐지

• 벨만-포드 알고리즘은 한 노드에서 다른 노드까지의 최단 경로를 많아봐야 V-1개의 간선을 지난다는 가정을 세운다. → 최단 경로가 V-1개보다 많은 간선을 지나게 된다면 음의 사이클이 존재한다는 의미이다 !