[그래프] 벨만-포드

✔ 벨만-포드

벨만-포드란?

• 그래프에서 특정 출발 노드에서 다른 모든 노드까지의 최단 거리를 구하는 알고리즘
• 음수 가중치 엣지가 있어도 수행할 수 있음
• 최단 거리를 구하는 문제보다 음수 사이클을 판단하는 문제에 더 빈번하게 사용
• V는 노드 수, E는 엣지 수일때, 시간 복잡도는 O(VE)

벨만-포드 과정

1. 엣지를 중심으로 동작하므로 엣지 리스트로 그래프를 표현
2. 최단 거리 배열을 만들고, 출발 노드는 0, 이 외의 노드는 무한으로 초기화
3. 출발 노드를 1로 선택
4. 선택된 노드에서 연결된 엣지의 값을 바탕으로 다른 노드의 값을 업데이트
   • D[s] != ∞이며 D[e] > D[s] + w일 때 D[e] = D[s] + w
   • 노드 개수가 N이고, 음수 사이클이 없을 때
     특정 두 노드의 최단 거리를 구성할 수 있는 엣지의 최대 갯수는 N - 1이기 때문에
     최단 거리 배열에서 노드 개수 - 1 만큼 업데이트 반복
   • 음수 사이클이 없을 때 N - 1번 엣지 사용 횟수를 반복하면 출발 노드와 모든 노드 간의 최단 거리를 구할 수 있게 됨
5. 모든 엣지를 한 번씩 다시 사용해 업데이트되는 노드가 발생하는지 확인
   • 만약 업데이트되는 노드가 있다면 음수 사이클이 있다는 뜻이므로
     정답 배열이 무의미하고 최단 거리를 찾을 수 없는 그래프라는 뜻
   • 음수 사이클이 존재하면 이 사이클을 무한하게 돌수록 가중치가 계속 감소하므로 최단 거리를 구할 수 없음

출발 노드가 4일 때

엣지 사용 횟수 1

엣지 사용 횟수 2

앳지 사용 횟수 3

음수 사이클 유무 확인

 

Do it! 알고리즘 코딩테스트 with JAVA

https://inf.run/w9Tn