1. Bellman-Ford가중 유향 그래프에서 최단 경로 문제를 푸는 알고리즘단일 출발점에서 모든 정점까지의 최단 거리를 구함✅ 음수 간선 허용✅ 음수 사이클 판별 가능 2. 동작 원리정점의 갯수 - 1 번 완화를 반복 수행함➡️ 최종적으로 출발지에서 모든 정점까지의 최단 거리를 구할 수 있음 초기화✅ 자기 자신으로 가는 최단 거리 = 0✅ 다른 정점으로 가는 최단 거리 = INF (도착 못함) 간선 완화최대 간선 수 = 정점의 갯수-1 (사이클이 일어나지 않는다는 가정)✅ 점점 최단거리가 갱신됨 음수 사이클 검사사이클을 한 바퀴 돌 때마다 전체 비용이 계속 줄어드는 사이클✅ 사이클을 많이 돌수록 총 가중치는 무한히 작아짐✅ 즉, 최단경로가 없다 볼 수 있음➡️ 모든 간선에 대해서 간선의 도착지로 가는..