벨만-포드그래프에서 최단 거리를 구하는 알고리즘특정 출발 노드에서 다른 모든 노드까지의 최단 경로 탐색 - 다익스트라와 같음음수 가중치 에지가 있어도 수행이 가능하다.전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있음시간복잡도는 O(VE) 💡 벨만-포드 알고리즘의 핵심 이론1. 에지리스트로 그래프를 구현하고 최단 경로 리스트 초기화하기* 에지리스트는 일반적으로 노드 변수 2개(start, end)와 가중치 변수로 구성되어있다. 2. 모든 에지를 확인해 정답 리스트 업데이트하기최단 거리 리스트에서 업데이트 반복 횟수는 노드-1 개이다.음수 사이클이 없을 때 특정 두 노드의 최단 거리를 구성할 수 있는 에지의 최대 개수는 N-1이기 때문이다. 모든 에지 E = (s, e, w)에서 다음 조건을 ..
