공부한 내용 기록하기 공부한 내용 기록하기

1. 벨만-포드 알고리즘이란?벨만-포드 알고리즘(Bellman-Ford Algorithm)은 가중치 그래프에서 한 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이다. 다익스트라 알고리즘과 유사하지만, 음수 가중치를 포함한 그래프에서도 동작한다.이 알고리즘은 그래프의 모든 간선을 여러 번 확인하며 최단 경로를 반복적으로 갱신하는 방식으로 동작한다. 특히 음수 가중치를 처리할 수 있으며, **음수 사이클(Negative Cycle)**이 있는지도 판별할 수 있다.1.1 벨만-포드 알고리즘의 특징음수 가중치 허용: 음수 가중치를 포함한 그래프에서 사용 가능음수 사이클 탐지: 음수 가중치의 무한 루프 발생 여부 확인 가능시간 복잡도: O(V × E) (V는 정점 수, E는 간선 수)2. 벨만-포드 알..