πŸ“š λͺ©μ°¨

μš”μ•½

1. 벨만-ν¬λ“œ(Bellman-ford-moore)

1. 벨만-ν¬λ“œ

κΈ°λŠ₯ νŠΉμ§• μ‹œκ°„ λ³΅μž‘λ„(λ…Έλ“œ 수: V, 에지 수: E)
νŠΉμ • 좜발 λ…Έλ“œμ—μ„œ λ‹€λ₯Έ λͺ¨λ“  λ…Έλ“œκΉŒμ§€μ˜ μ΅œλ‹¨ 경둜 탐색 - 음수 κ°€μ€‘μΉ˜ 에지가 μžˆμ–΄λ„ μˆ˜ν–‰ν•  수 있음

2. 벨만-ν¬λ“œμ˜ 핡심 이둠

  1. κ·Έλž˜ν”„μ˜ 정보(μ‹œμž‘λ…Έλ“œ, μ’…λ£Œ λ…Έλ“œ, λΉ„μš©)을 tuple둜 λ°›μ•„ μ €μž₯ν•œλ‹€.

1.png

인덱슀 인접 νŠœν”Œ κ°’(μ‹œμž‘, μ’…λ£Œ, λΉ„μš©)
0 (1, 2, 4)
1 (1, 3, 3)
2 (2, 3, -4)
3 (3, 1, -2)
  1. μ΅œμ†ŒλΉ„μš©λ²‘ν„°λ₯Ό λ§Œλ“€μ–΄μ„œ μ‹œμž‘ λ…Έλ“œ(μ—¬κΈ°μ„œλŠ” 1번)의 λΉ„μš©μ€ 0, λ‚˜λ¨Έμ§€λŠ” MAX둜 μ±„μ›Œμ€€λ‹€.
1 2 3
0 MAX MAX