codingbutterfly
블로그 이미지

Home

Write

Setting

About Me

  • 분류 전체보기 (67)
    • Alrogithm (53)
      • 백준(BOJ) (2)
      • 구름(GOORM) (32)
      • 프로그래머스(PROGRAMMERS) (18)
      • 유형별 basic (1)
    • React-native (12)
      • KakaoLogin (4)
      • AWS (2)
      • Spotify (1)
    • C++ (1)
dark
no image
벨만-포드 알고리즘(Bellman-Ford Algorithm)
벨만-포드 개념 벨만 포드 알고리즘은 가중치가 존재하는 그래프에서 최단 경로를 구하고자 할 때 사용할 수 있는 알고리즘이다. 보통 위와 같은 유형의 문제를 풀기 위해 다익스트라 알고리즘을 먼저 학습한다. 결론부터 말하자면 다익스트라 알고리즘의 경우 음수 간선이 존재하는 경우 문제를 해결하지 못 할 수 있다. 다익스트라 음수 간선 위에서 다익스트라의 경우 음수 간선이 존재하면 문제를 해결하지 못한다고 하지 않았고 못 할 수 도 있다고 했다. 아래의 그래프를 통해 자세히 이해해보자. 단순한 음의 간선 : s -> a -> b -> g 경로에 -4(a -> b) 음의 간선이 있어도 문제가 발생하지 않음 순환하지 않는 싸이클 : s -> c > -> d 경로 이후 d->c로 가는 경우 -3 음의 간선이 있지만 ..
2023.02.08
Alrogithm/유형별 basic
Prev 1 Next
uTube · Designed By ushin20

티스토리툴바

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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