728x90
반응형
벨만-포드 bellman-ford-moore
그래프에서 최단 거리를 구하는 알고리즘
특정 출발 노드에서 다른 모든 노드까지의 최단 경로 탐색
음수 가중치 에지가 있어도 수행할 수 있음
전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있음
1. 에지 리스트로 그래프를 구현하고 최단 경로 리스트 초기화하기
출발노드0, 나머지는 무한으로 초기화
2. 모든 에지를 확인해 정답 리스트 업데이트 하기
노드개수 -1 만큼 반복:
에지 개수 만큼 반복:
E = (s, e, w)에서 아래 조건을 만족하면 업데이트
D[s] != 무한, D[e] > D[s] + w 이면, D[e] = D[s] + w
3. 음수 사이클 유무 확인하기
모든 에지를 다시 사용하여 업데이트되는 노드가 있는지 확인
(음수 사이클이 발생하는 것임)
에지 개수만큼 반복:
같은 조건에서 변하는 노드 존재 여부 확인
반응형
