Dijkstra Algorithm
μ΅λ¨ κ²½λ‘
μ΅λ¨ κ²½λ‘ μ μ
: κ°μ μ κ°μ€μΉκ° μλ κ·Έλνμμ λ μ μ μ¬μ΄μ κ²½λ‘λ€ μ€μ κ°μ μ κ°μ€μΉμ ν©μ΄ μ΅μμΈ κ²½λ‘
νλμ μμ μ μ μμ λ μ μ κΉμ§μ μ΅λ¨ κ²½λ‘ (one to all)
λ€μ΅μ€νΈλΌ (dijkstra) μκ³ λ¦¬μ¦
μμ κ°μ€μΉλ₯Ό νμ©νμ§ μμ
벨λ§-ν¬λ (Bellman-Ford) μκ³ λ¦¬μ¦
μμ κ°μ€μΉ νμ©
λͺ¨λ μ μ λ€μ λν μ΅λ¨ κ²½λ‘
νλ‘μ΄λ-μμ¬ (Floyd-Warshall) μκ³ λ¦¬μ¦
Dijkstra Algorithm
μμ μ μ μμ κ±°λ¦¬κ° μ΅μμΈ μ μ μ μ νν΄ λκ°λ©΄μ μ΅λ¨ κ²½λ‘λ₯Ό ꡬνλ λ°©μ
μμ μ μ (s)μμ λ μ μ (t) κΉμ§μ μ΅λ¨ κ²½λ‘μ μ μ xκ° μ‘΄μ¬νλ€
μ΄λ, μ΅λ¨ κ²½λ‘λ sμμ xκΉμ§μ μ΅λ¨ κ²½λ‘μ x μμ t κΉμ§μ μ΅λ¨ κ²½λ‘λ‘ κ΅¬μ±λλ€
νμ (greedy) κΈ°λ²μ μ¬μ©ν μκ³ λ¦¬μ¦μΌλ‘ MSTμ
Prim Algorithm
κ³Ό μ μ¬νλ€μΈμ νλ ¬ κ·Έλνμ μμ μ μ μ΄ μ£Όμ΄μ‘μ λ, λ€μ΅μ€νΈλΌ μκ³ λ¦¬μ¦μ μ¬μ©νλ©΄ μμ μ μ μμ λͺ¨λ μ μ μΌλ‘ κ°λ μ΅λ¨ 거리λ₯Ό ꡬν μ μλ€
μκ° λ³΅μ‘λ
μκ° λ³΅μ‘λ
: O(logN)
ꡬν ν΄λ³΄κΈ°
Dijkstra + μΈμ 리μ€νΈ
"""
6 11
0 1 3
0 2 5
1 2 2
1 3 6
2 1 1
2 3 4
2 4 6
3 4 2
3 5 3
4 0 3
4 5 6
κ²°κ³Ό
[0, 3, 5, 9, 11, 12]
"""
# dist, selected λ°°μ΄ μ€λΉ
# μμμ μ ν
# λͺ¨λ μ μ μ΄ μ νλ λ κΉμ§
# μμ§ μ νλμ§ μκ³ distμ κ°μ΄ μ΅μμΈ μ μ : u
# μ μ uμ μ΅λ¨κ±°λ¦¬ κ²°μ
# μ μ uμ μΈμ ν μ μ μ λν΄μ κ°μ μν
V, E = map(int, input().split())
adj = {i:[] for i in range(V)}
for i in range(E):
s, e, c = map(int, input().split())
adj[s].append([e,c]) #λ°©ν₯ κ·ΈλνλΌμ
INF = float('inf')
dist = [INF]*V
selected = [False]*V
dist[0] = 0
cnt = 0
while cnt <V:
# distκ° μ΅μμΈ μ μ μ°ΎκΈ°
MIN = INF
for i in range(V):
if not selected[i] and dist[i] < MIN:
MIN = dist[i]
u = i
# κ²°μ
selected[u] = True
cnt += 1
# κ°μ μν
for w, cost in adj[u]: # λμ°©μ μ , κ°μ¦μΉ
if dist[w] > dist[u] + cost:
dist[w] = dist[u] + cost
print(dist) # [0, 3, 5, 9, 11, 12]
Last updated
Was this helpful?