벨만-포드 (Bellman-Ford-moore)

2025. 6. 5. 13:16·PS/알고리즘
목차
  1. 핵심 이론
  2. 1. 에지 리스트로 그래프 표현 및 최단 경로 배열 초기화
  3. 2. 모든 에지를 확인해 정답 배열 갱신
  4. 3. 음수 사이클 유무 확인
  5. 관련 문제
728x90

벨만 포드 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘으로, 주요 특징은 다음과 같음

기능 특징 시간 복잡도(노드: V, 에지: E)
특정 출발 노드에서 다른 모든 노드까지의 최단 경로 - 음수 가중치 간선이 있어도 수행
- 음수 사이클의 존재 여부 판단 가능
O(VE)

핵심 이론

벨만 포드 알고리즘은 다음 3단계의 원리로 동작

1. 에지 리스트로 그래프 표현 및 최단 경로 배열 초기화

벨만 포드 알고리즘은 간선을 중심으로 동작하므로 그래프를 간선 리스트로 구현

또한 최단 경로 배열은 출발 노드는 0, 나머지는 무한대로 초기화


2. 모든 에지를 확인해 정답 배열 갱신

최단 거리 배열에서 갱신 반복 횟수는 노드 개수 -1

∵ 노드 개수가 N이고, 음수 사이클이 없을 때 특정 두 노드의 최단 거리를 구성할 수 있는 간선의 최대개수는 N-1

특정 간선 E=(s, e, w)에서 다음 조건을 만족하면 갱신함

📌 갱신 조건과 방법
D[S] != INF 이며, D[E] > D[S] + W인 경우,  D[E] = D[S] + W

음수 사이클이 없을 때 N-1번 간선 사용 횟수를 반복하면 출발 노드와 모든 노드 간의 최단 거리를 알려 주는 정답 배열이 도출됨

완성 후, 이 그래프에 음수 사이클이 존재하는지 확인해야 함


3. 음수 사이클 유무 확인

음수 사이클 유무를 확인하기 위해 모든 간선을 한 번씩 다시 사용해 갱신되는 노드가 있는지 확인

만일 갱신되는 노드가 있다면 음수 사이클이 존재한다는 뜻이 됨
👉 이전에 도출한 정답 배열이 무의미 하고 최단 거리를 찾을 수 없는 그래프임

📌 음수 사이클이 존재하면, 이 사이클을 무한하게 돌수록 가중치가 계속 감소하므로 최단 거리를 구할 수 없음

실제 코딩 테스트에서는 벨만 포드 알고리즘을 사용해 최단 거리를 구하는 것보다 음수 사이클을 판별하는 문제로 빈번하게 출제됨

∴ 마지막에 한 번 더 모든 간선을 사용해 업데이트되는 노드가 존재하는지 확인해야 함!


관련 문제

[백준 - 타임머신] (https://www.acmicpc.net/problem/11657)

[백준 - 오민식의 고민] (https://www.acmicpc.net/problem/1219)

728x90
  1. 핵심 이론
  2. 1. 에지 리스트로 그래프 표현 및 최단 경로 배열 초기화
  3. 2. 모든 에지를 확인해 정답 배열 갱신
  4. 3. 음수 사이클 유무 확인
  5. 관련 문제
'PS/알고리즘' 카테고리의 다른 글
  • 트리 (Tree)
  • 최소 신장 트리 (Minimum Spanning Tree)
  • 플로이드-워셜 (Floyd-warshall)
  • 다익스트라 (Dijkstra)
0woy
0woy
Algorithm, CS, Web 등 배운 내용을 기록합니다.
  • 0woy
    0woy dev
    0woy
  • 전체
    오늘
    어제
  • 🌐 LANGUAGE
    • 분류 전체보기 (80)
      • Backend (21)
        • JAVA (7)
        • DB (11)
        • Spring (1)
        • Spring Security (2)
      • Computer Science (22)
        • 네트워크 (9)
        • 운영체제 (5)
        • 보안 (7)
      • Frontend (15)
        • HTML5 (1)
        • CSS (1)
        • JS (4)
        • Vue 3 (9)
      • PS (16)
        • LeetCode (2)
        • Baekjoon (1)
        • Programmers (1)
        • 알고리즘 (12)
      • Dev Trivia (6)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    function
    Spring
    tcp
    Props
    https
    java
    dfs
    select
    set
    가용성
    leetcode
    DP
    security
    PreparedStatement
    비밀키
    JDBC
    Graph
    그래프
    Filter
    속성
    JS
    트리
    javascript
    공개키
    CA
    BFS
    대칭키
    Vue3
    shortestpath
    RDB
  • 최근 댓글

  • 최근 글

  • 250x250
  • hELLO· Designed By정상우.v4.10.3
0woy
벨만-포드 (Bellman-Ford-moore)

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.