그래프 - 벨만 포드, 플로이드 워셜

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

기능	특징	시간 복잡도(노드 수: V, 엣지 수: E)
특정 출발 노드에서 다른 모든 노드까지의 최단 경로 탐색	음수 가중치 엣지가 있어도 수행할 수 있음 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있음	O(VE)

 

벨만 포드 알고리즘의 핵심 이론

1. 엣지 리스트로 그래프를 구현하고 최단 경로 리스트 초기화하기

(벨만 포드 알고리즘은 엣지를 중심으로 동작하므로 그래프를 엣지 리스트로 구현합니다.)

(최단 경로 리스트의 출발 노드는 0, 나머지 노드는 무한대로 초기화)

2. 모든 엣지를 확인해 정답 리스트 업데이트하기

(최단 거리 리스트에서 업데이트 반복 횟수는 노드 개수 - 1이다.)

(노드의 개수가 N이고, 음수 사이클이 없을 때 특정 두 노드의 최단 거리를 구성할 수 있는 엣지의 최대 개수가 N - 1이기 때문이다)

3. 음수 사이클 유무 확인하기