선행지식

• Graph
• Dijkstra

기본 개념

벨만 포드 알고리즘은 시작 정점 하나에서 모든 정점까지의 최단 거리를 구하는 알고리즘이다.

다익스트라와 달리 음수 가중치 간선을 허용하고, 음수 사이클 존재 여부까지 판별할 수 있다.

예시 워크스루

시작 정점을 1로 둔다.

• 간선: 1→2(4), 1→3(5), 2→3(-2), 2→4(6), 3→4(3), 3→5(4), 4→5(2)

초기화

• 거리 배열: [0, INF, INF, INF, INF]

1회차 전체 간선 완화

• 2: 4
• 3: min(5, 4-2)=2
• 4: min(INF, 2+3)=5
• 5: min(INF, 2+4)=6
• 결과: [0, 4, 2, 5, 6]