[알고리즘] 벨만-포드 (Bellman-Ford)

최단 경로

 

[알고리즘 소개]

가중치가 존재하는 그래프에서 출발지가 정해졌을 때 해당 출발지에서 다른 정점으로 이동하는 최단 경로를 구하는 알고리즘.

 

 

[알고리즘 특징]

• 음수 가중치 가능
• 모든 간선에 대해 조사
• 음수 사이클 판정 가능

[코딩 방법]

1. 간선에 대한 정보를 저장할 클래스(구조체) 생성, 배열에 저장
2. dp용 배열 생성, INF로 배열을 채우고 시작점에 대해서만 0으로 초기화
3. V - 1회동안 모든 간선을 확인하면서 최단경로 갱신
4. 이후 V회동안 모든 간선에 대해 더 확인하면서 음수 사이클이 발생했는지 확인
5. 음수 사이클의 존재만 알고 싶다면 1회만 모든 간선에 대해 확인해도 무방

[시간 복잡도]

$O(VE)$

 

 

[공부용 링크]

youtu.be/Ppimbaxm8d8