✏️ μ•Œκ³ λ¦¬μ¦˜/Graph

4. Bellman-Ford(벨만 ν¬λ“œ) : μ΅œλ‹¨ 경둜 탐색 - 2

2021. 3. 7. 15:34
λͺ©μ°¨
  1. Bellman Ford (벨만 ν¬λ“œ)
  2. μ΅œλ‹¨ 경둜 탐색 - 2

Bellman Ford (벨만 ν¬λ“œ)

μ΅œλ‹¨ 경둜 탐색 - 2

 

μ˜€λŠ˜μ€ μ§€λ‚œλ²ˆ λ‹€μ΅μŠ€νŠΈλΌμ— 이어 μ΅œλ‹¨ 경둜λ₯Ό νƒμƒ‰ν•˜λŠ” μ•Œκ³ λ¦¬μ¦˜μ„ μ •λ¦¬ν•˜λ €κ³  ν•œλ‹€.

μ§€λ‚œλ²ˆ λ‹€μ΅μŠ€νŠΈλΌ ν¬μŠ€νŒ…μ—μ„œ λ‹€μ΅μŠ€νŠΈλΌλŠ” 음의 사이클이 μžˆλŠ” κ·Έλž˜ν”„μ—μ„œλŠ” μ‚¬μš©μ΄ λΆˆκ°€λŠ₯ν•˜λ‹€κ³  ν•˜μ˜€λ‹€.

κ·Έ μ΄μœ λŠ” λ¬΄μ—‡μΌκΉŒ?

 

μš°μ„ , λ‹€μŒκ³Ό 같은 κ·Έλž˜ν”„μ˜ μ‹œμž‘ 정점이 A라고 ν–ˆμ„ λ•Œμ˜ μ΅œλ‹¨ 경둜λ₯Ό κ΅¬ν•΄λ³΄μž.

 

[μ˜ˆμƒ κ²°κ³Ό]

A : 0

B : -4

C : 3

D : -7

E : 1

F : -3

 

[μ‹€μ œ κ²°κ³Ό]

 

μ‹œμž‘ μ •μ μ—μ„œ μ΄μƒν•œ 값이 좜λ ₯λ˜λŠ” 것을 λ³Ό 수 μžˆλ‹€.


λ‹€λ₯Έ μ˜ˆμ‹œλ₯Ό 보자.

 

 

[μ˜ˆμƒ κ²°κ³Ό]

A : 0

B : 2 ( μž¬λ°©λ¬Έμ„ ν•˜μ§€ μ•ŠλŠ”λ‹€κ³  κ°€μ •)

C : 5

D : 1

E : 3

 

[μ‹€μ œ κ²°κ³Ό]

 

μ—­μ‹œ, E μ •μ μ—μ„œ μ΄μƒν•œ 값이 좜λ ₯λ˜λŠ” 것을 λ³Ό 수 μžˆλ‹€.

 

μ΄μœ κ°€ 뭘까?

 

μ΄μœ λŠ” λ‹€μ΅μŠ€νŠΈλΌμ˜ 경우 λ°©λ¬Έν•œ 정점과 μ—°κ²°λœ 정점듀을 νƒμƒ‰ν•˜λ©΄μ„œ

μ΅œλ‹¨ κ²½λ‘œκ°€ μ €μž₯된 distance λ³€μˆ˜μ™€ κ°€μ€‘μΉ˜λ₯Ό λΉ„κ΅ν•˜μ—¬ κ°€μ€‘μΉ˜κ°€ 더 μž‘μ€ 경우

distance λ³€μˆ˜λ₯Ό κ°±μ‹ ν•΄μ£ΌλŠ” λ°©μ‹μœΌλ‘œ κ΅¬ν˜„λ˜μ–΄μžˆλ‹€.

 

이후 λ°©λ¬Έν•œ 정점을 λ‹€μ‹œ λ°©λ¬Έν•˜μ§€ μ•Šλ„λ‘ λ°©λ¬Έ μ²˜λ¦¬ν•΄μ£ΌλŠ”λ°

이 κ³Όμ •μ—μ„œ 음의 사이클에 μ‘΄μž¬ν•˜κ±°λ‚˜ 음의 사이클을 κ±°μΉ˜λŠ” 경우

음의 사이클에 고립(?) λ˜μ–΄ 비정상적인 값이 좜λ ₯될 수 μžˆλ‹€.

 

μœ„μ—μ„œ λ³Έ κ²ƒμ²˜λŸΌ κ°€μ€‘μΉ˜μ— 음의 값이 μžˆλŠ” 경우 λ‹€μ΅μŠ€νŠΈλΌ μ•Œκ³ λ¦¬μ¦˜μ€ λΉ„μ •μƒμ μœΌλ‘œ 좜λ ₯될 κ°€λŠ₯성이 μžˆλ‹€.

이λ₯Ό ν•΄κ²°ν•˜κΈ° μœ„ν•œ μ•Œκ³ λ¦¬μ¦˜μ΄ 였늘 μ„€λͺ…ν•  벨만 ν¬λ“œ μ•Œκ³ λ¦¬μ¦˜μ΄λ‹€.

 

벨만 ν¬λ“œ μ•Œκ³ λ¦¬μ¦˜μ€ κ°€μ€‘μΉ˜κ°€ 음의 값이 μ‘΄μž¬ν•΄λ„ μ •μƒμ μœΌλ‘œ μ΅œλ‹¨ 경둜λ₯Ό ꡬ할 수 μžˆλ‹€.

뿐만 μ•„λ‹ˆλΌ  κ·Έλž˜ν”„ λ‚΄μ˜ 음의 사이클을 탐지할 수 μžˆλ‹€.

 

λ‹€μ΅μŠ€νŠΈλΌμ™€ κ°±μ‹  방법은 λ˜‘κ°™λ‹€.

λ‹€λ₯Έ 점은 탐색 방법인데 "μ΅œλ‹¨ κ²½λ‘œλŠ” 사이클을 포함할 수 μ—†λ‹€." λΌλŠ” μ „μ œμ‘°κ±΄μ„ κ°–κ³  μ‹œμž‘ν•œλ‹€.

(Ex. 정점이 3개인 경우 간선은 2κ°œκ°€ 쑴재.)

λ”°λΌμ„œ λͺ¨λ“  정점을 (μ •μ μ˜ 개수 - 1)번 λ°˜λ³΅μ„ 톡해 κ°±μ‹ ν•œλ‹€. 

이후 ν•œλ²ˆ 더 갱신을 μ§„ν–‰ν•˜λŠ”λ° 이 κ³Όμ •μ—μ„œ μ΅œλ‹¨ κ²½λ‘œκ°€ 갱신이 λœλ‹€λ©΄ 음의 사이클이 μ‘΄μž¬ν•˜λŠ” 경우라고 생각할 수 μžˆλ‹€. 

 

μœ„μ˜ κ°œλ…μ„ 파이썬으둜 κ΅¬ν˜„ν•΄λ³΄μ•˜λ‹€.

 

μœ„μ—μ„œ μ–ΈκΈ‰ν•œ κ·Έλž˜ν”„λ‘œ μž…λ ₯ 값을 μ£Όλ©΄ μ΄λ‘ μƒμœΌλ‘œ κ΅¬ν•œ λ‹΅κ³Ό 동일 ν•œ 것을 λ³Ό 수 μžˆλ‹€.

 

[Input]

6 9
A B C D E F
A B -4
A C 3
A E 3
A F 3
B D -3
B E 5
C F -1
D A -1
D F 4
A

 

[Output]

 

μ§€κΈˆκΉŒμ§€λŠ” νŠΉμ •ν•œ μ •μ μ—μ„œ λ‹€λ₯Έ μ •μ κΉŒμ§€μ˜ μ΅œλ‹¨ 경둜λ₯Ό νƒμƒ‰ν–ˆλ‹€λ©΄

λ‹€μŒμ—λŠ” λͺ¨λ“  μ •μ μ—μ„œ λͺ¨λ“  μ •μ κΉŒμ§€μ˜ μ΅œλ‹¨ 경둜λ₯Ό νƒμƒ‰ν•˜λŠ” ν”Œλ‘œμ΄λ“œ 와샬 μ•Œκ³ λ¦¬μ¦˜μ„ μ„€λͺ…ν•˜λ„λ‘ ν•˜κ² λ‹€.

 

μΆ©λ‚¨λŒ€ν•™κ΅ 컴퓨터곡학과 μ΄μ˜μ„ κ΅μˆ˜λ‹˜μ˜ μ•Œκ³ λ¦¬μ¦˜ μˆ˜μ—…κ³Ό λ™λΉˆλ‚˜μ˜ 유튜브 κ°•μ’Œ(https://youtu.be/611B-9zk2o4)λ₯Ό μ°Έκ³ ν–ˆμŠ΅λ‹ˆλ‹€.

μ €μž‘μžν‘œμ‹œ (μƒˆμ°½μ—΄λ¦Ό)

'✏️ μ•Œκ³ λ¦¬μ¦˜ > Graph' μΉ΄ν…Œκ³ λ¦¬μ˜ λ‹€λ₯Έ κΈ€

6. Union Find(ν•©μ§‘ν•© μ°ΎκΈ°) : MST - 1  (0) 2021.05.30
5. Floyd Warshall(ν”Œλ£¨μ΄λ“œ 와샬) : μ΅œλ‹¨ 경둜 탐색 - 3  (0) 2021.03.31
3. Dijsktra(λ‹€μ΅μŠ€νŠΈλΌ) : μ΅œλ‹¨ 경둜 탐색 - 1  (0) 2021.03.02
2. DFS(Depth-Find-Search) : 깊이 μš°μ„  탐색  (0) 2021.01.22
1. BFS(Breath-Find-Search) : λ„ˆλΉ„ μš°μ„  탐색  (0) 2021.01.21
  1. Bellman Ford (벨만 ν¬λ“œ)
  2. μ΅œλ‹¨ 경둜 탐색 - 2
'✏️ μ•Œκ³ λ¦¬μ¦˜/Graph' μΉ΄ν…Œκ³ λ¦¬μ˜ λ‹€λ₯Έ κΈ€
  • 6. Union Find(ν•©μ§‘ν•© μ°ΎκΈ°) : MST - 1
  • 5. Floyd Warshall(ν”Œλ£¨μ΄λ“œ 와샬) : μ΅œλ‹¨ 경둜 탐색 - 3
  • 3. Dijsktra(λ‹€μ΅μŠ€νŠΈλΌ) : μ΅œλ‹¨ 경둜 탐색 - 1
  • 2. DFS(Depth-Find-Search) : 깊이 μš°μ„  탐색
kodo_o
kodo_o
iOS κΏ€μžΌ!
🍎🍏iOS κΏ€μžΌ!
kodo_o
🍎🍏
kodo_o
전체
였늘
μ–΄μ œ
  • λΆ„λ₯˜ 전체보기 (149)
    • πŸ”¨ ν”„λ‘œμ νŠΈ (0)
      • TP 1 (0)
      • WhiteHCCTV (0)
      • FootPrint (0)
    • πŸ’» 개발 (63)
      • iOS (30)
      • Android (6)
      • Kotlin (4)
      • Flutter (9)
      • Node.js (5)
      • Architecture (1)
      • 였늘의 μ‚½μ§ˆ (7)
      • μ—λŸ¬μ™€μ˜ 동침 (1)
    • ✏️ μ•Œκ³ λ¦¬μ¦˜ (6)
      • Graph (6)
      • String (0)
      • Sort (0)
    • ✍️ μ½”ν…Œ μ€€λΉ„ (44)
      • Math (1)
      • Implementation (3)
      • String (3)
      • Brute Force (5)
      • Back Tracking (7)
      • Greedy (0)
      • Dynamic Programming (13)
      • Binary Search (1)
      • DFS, BFS (5)
      • Shortest Path (2)
      • Two Pointer (4)
      • MST (0)
    • πŸ“š CS (6)
      • Operating System (6)
    • ⛹️ 라이프 (30)
      • 2020 κ²¨μšΈλ°©ν•™ λͺ¨κ°μ½”(개인) (12)
      • 2021 여름방학 λͺ¨κ°μ½”(개인) (6)
      • μ½”λ”© ν…ŒμŠ€νŠΈ (1)
      • 회고 (10)

λΈ”λ‘œκ·Έ 메뉴

  • ν™ˆ
  • κΉƒν—ˆλΈŒ

인기 κΈ€

졜근 κΈ€

졜근 λŒ“κΈ€

hELLO Β· Designed By μ •μƒμš°.
kodo_o
4. Bellman-Ford(벨만 ν¬λ“œ) : μ΅œλ‹¨ 경둜 탐색 - 2
μƒλ‹¨μœΌλ‘œ

ν‹°μŠ€ν† λ¦¬νˆ΄λ°”

단좕킀

λ‚΄ λΈ”λ‘œκ·Έ

λ‚΄ λΈ”λ‘œκ·Έ - κ΄€λ¦¬μž ν™ˆ μ „ν™˜
Q
Q
μƒˆ κΈ€ μ“°κΈ°
W
W

λΈ”λ‘œκ·Έ κ²Œμ‹œκΈ€

κΈ€ μˆ˜μ • (κΆŒν•œ μžˆλŠ” 경우)
E
E
λŒ“κΈ€ μ˜μ—­μœΌλ‘œ 이동
C
C

λͺ¨λ“  μ˜μ—­

이 νŽ˜μ΄μ§€μ˜ URL 볡사
S
S
맨 μœ„λ‘œ 이동
T
T
ν‹°μŠ€ν† λ¦¬ ν™ˆ 이동
H
H
단좕킀 μ•ˆλ‚΄
Shift + /
⇧ + /

* λ‹¨μΆ•ν‚€λŠ” ν•œκΈ€/영문 λŒ€μ†Œλ¬Έμžλ‘œ 이용 κ°€λŠ₯ν•˜λ©°, ν‹°μŠ€ν† λ¦¬ κΈ°λ³Έ λ„λ©”μΈμ—μ„œλ§Œ λ™μž‘ν•©λ‹ˆλ‹€.