๋ค์ต์คํธ๋ผ (Dijkstra)
๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ด๋
โ ์์ ๊ฐ์ค์น๊ฐ ์๋ ๊ทธ๋ํ์ ํ ์ ์ ์์ ๋ชจ๋ ์ ์ ๊น์ง์ ์ต๋จ๊ฑฐ๋ฆฌ๋ฅผ ๊ฐ๊ฐ ๊ตฌํ๋ ์๊ณ ๋ฆฌ์ฆ
๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ ์๋ฆฌ
ใใใ* P[a][b]: a์ b ์ฌ์ด์ ๊ฑฐ๋ฆฌ
- ์ถ๋ฐ์ ์ผ๋ก๋ถํฐ ์ต๋จ๊ฑฐ๋ฆฌ๋ฅผ ์ ์ฅํ ๋ฐฐ์ด distance[v]์ ๋ง๋ค๊ณ ์ถ๋ฐ ๋ ธ๋๋ 0, ๋๋จธ์ง ๋ ธ๋๋ค์ ์ถฉ๋ถํ ํฐ ๊ฐ์ผ๋ก ์ด๊ธฐํ ํ๋ค.
- ํ์ฌ ๋ ธ๋ Current๋ฅผ ์ถ๋ฐ ๋ ธ๋์ ๋ฒํธ๋ก ์ค์ ํ๋ค.
- Current๋ก๋ถํฐ ๊ฐ ์ ์๋ ์์์ ๋ ธ๋ Next์ ๋ํด distance[Current] + P[Current][Next](A๋ฅผ ๊ฑฐ์ณ์ B๋ก ๊ฐ๋ ์ต๋จ๊ฑฐ๋ฆฌ)์ distance[Next](ํ์ฌ๊น์ง ์๋ ค์ง B์ ์ต๋จ ๊ฑฐ๋ฆฌ)์ ๊ฐ์ ๋น๊ตํด์ ์งง์ ๊ฐ(์งง์ ๊ฒฝ๋ก)๋ก ๊ฐฑ์ ํ๋ค.
- Current์ ๋ชจ๋ ์ด์๋ ธ๋ Next์ ๋ํด 3 ์ ์ํํ๋ค.
- Current์ ์ํ๋ฅผ ‘visited=True’๋ก ๋ฐ๊ฟ์ค๋ค. (Current๋ ๋ ์ด์ ์ฌ์ฉํ์ง ์๋๋ค.)
- visited == False์ธ ๋ ธ๋ ์ค ์ถ๋ฐ์ ์ผ๋ก๋ถํฐ ๊ฑฐ๋ฆฌ๊ฐ ๊ฐ์ฅ ์งง์ ๋ ธ๋๋ฅผ Current๋ก ์ค์ ํ๋ค.
- ๋์ฐฉ ๋ ธ๋๊ฐ 'visited == True’๊ฐ ๋๊ฑฐ๋, ๋ ์ด์ ๋ฏธ๋ฐฉ๋ฌธ ๋ ธ๋๋ฅผ ์ ํํ ์ ์์ ๋๊น์ง 3 ~ 6์ ๊ณผ์ ์ ๋ฐ๋ณตํ๋ค.
๊ทธ๋ฆผ์ผ๋ก ๋ํ๋ธ ๋ค์ต์คํธ๋ผ
![image](https://user-images.githubusercontent.com/109324637/192918650-da132eb8-df2a-4b08-b812-a3908e180292.png)
์์ค์ฝ๋ (๊ธฐ๋ณธํํ: O(V^2))
# V: ์ ์ ์ ๊ฐ์, E: ๊ฐ์ ์ ๊ฐ์, start: ์ถ๋ฐ๋
ธ๋
V, E = map(int, input().split())
start = int(input())
# visited: ๋ฐฉ๋ฌธ ์ฌ๋ถ ํ์ ๋ฐฐ์ด
visited = [False for _ in range(V + 1)]
# distance: ์ต๋จ๊ฑฐ๋ฆฌ ํ
์ด๋ธ (์ถฉ๋ถํ ํฐ ๊ฐ์ผ๋ก ์ด๊ธฐํ)
distance = [float('INF')for _ in range(V + 1)]
# graph: ์ธ์ ๋ฆฌ์คํธ๋ก ๊ตฌํํ ๊ทธ๋ํ
graph = [[] for _ in range(V + 1)]
for _ in range(E):
node1, node2, weight = map(int, input().split())
graph[node1].append((node2, weight))
# ๋ฏธ๋ฐฉ๋ฌธ ๋
ธ๋ ์ค์์ ์ต๋จ๊ฑฐ๋ฆฌ์ธ ๋
ธ๋๋ฅผ ์ฐพ๋ ํจ์
def next_node():
min_val = float('INF')
idx = 0
# ๋ชจ๋ ์ ์ ์ ๋ํด ํ์
for i in range(1, V + 1):
# ๋ฏธ๋ฐฉ๋ฌธ ๋
ธ๋ ์ค ์ต๋จ๊ฑฐ๋ฆฌ ๋
ธ๋ ํ์
if distance[i] < min_val and not visited[i]:
min_val = distance[i]
idx = i
# ๋
ธ๋ ๋ฒํธ ๋ฐํ
return idx
# ๋ค์ต์คํธ๋ผ ํจ์
def dijkstra(start):
# ์ถ๋ฐ์ ๊ฑฐ๋ฆฌ ๋ฐ ๋ฐฉ๋ฌธ ํ์
distance[start] = 0
visited[start] = True
# ์ถ๋ฐ๋
ธ๋์ ์ธ์ ๋
ธ๋ ์ต๋จ๊ฑฐ๋ฆฌ ํ
์ด๋ธ ๊ฐฑ์
for adj in graph[start]:
distance[adj[0]] = adj[1]
# ๋๋จธ์ง ๋
ธ๋ ๋ชจ๋ ๋
ธ๋์ ๋ํด ๋ฐ๋ณต
for _ in range(V - 1):
# ๋ค์ ๋
ธ๋ ์ค์ ๋ฐ ๋ฐฉ๋ฌธ ํ์
current = next_node()
visited[current] = True
# ์ต๋จ ๊ฑฐ๋ฆฌ ๊ฐฑ์
for adj in graph[current]:
cost = distance[current] + adj[1]
if cost < distance[adj[0]]:
distance[adj[0]] = cost
return
# ์ถ๋ฐ์ ์ผ๋ก๋ถํฐ ๋ค์ต์คํธ๋ผ
dijkstra(start)
# ์ต๋จ๊ฑฐ๋ฆฌ ํ
์ด๋ธ ์ถ๋ ฅ
print(distance)
์ฐ์ ์์ ํ๋ฅผ ์ด์ฉํ ๋ค์ต์คํธ๋ผ (O(ElogE))
โ ๊ธฐ๋ณธ ํํ์ ๋ค์ต์คํธ๋ผ๋ ๋ค์ ๋
ธ๋๋ฅผ ํ์ํ๋ ๊ณผ์ ์์ ๋ชจ๋ ๋
ธ๋๋ฅผ ์ํํ๊ฒ ๋์ด O(V^2)์ ์๊ฐ ๋ณต์ก๋๋ฅผ ๊ฐ์ง๊ฒ ๋๋ค.
โ ์ฐ์ ์์ํ(ํํ)๋ฅผ ์ด์ฉํ๋ฉด ์ต๋จ๊ฑฐ๋ฆฌ์ ์ ์ ์ ๋ณด๋ฅผ ์ ์ฅํด๋๋ค๊ฐ ๋ฐ๋ก ๋ค์ ๋
ธ๋๋ฅผ ๋ฝ์๋ผ ์ ์๋ค. -> O(ElogE)์ ์๊ฐ๋ณต์ก๋
์์ค ์ฝ๋
import heapq
# ์ฐ์ ์์ ํ๋ฅผ ์ด์ฉํ ๋ค์ต์คํธ๋ผ
def dijkstra(start):
# ์ฐ์ ์์ํ ์ ์ธ
queue = []
# ์ฐ์ ์์ ํ์ (0(์ถ๋ฐ์ ๊ฑฐ๋ฆฌ), ์ถ๋ฐ์ ) ์ฝ์
heapq.heappush(queue, (0, start))
# ์ถ๋ฐ์ ๊ฑฐ๋ฆฌ ํ์
distance[start] = 0
# ์ฐ์ ์์ ํ๊ฐ ๋น ๋๊น์ง ์งํ
while queue:
# ์ต๋จ๊ฑฐ๋ฆฌ ์ ์ ์ถ์ถ
weight, node = heapq.heappop(queue)
# ํด๋น ์ ์ ์ด ์ต๋จ๊ฑฐ๋ฆฌ๊ฐ ๋ง์ ๊ฒฝ์ฐ
if distance[node] == weight:
# ์ธ์ ์ ์ ์ ๋ํด์ ์ต๋จ๊ฑฐ๋ฆฌ ๋น๊ตํด๊ฐ๋ฉด์ ๊ฐฑ์
for next in graph[node]:
cost = distance[node] + next[1]
# ์ต๋จ ๊ฑฐ๋ฆฌ ๊ฐฑ์ ํ ๊ฒฝ์ฐ
if cost < distance[next[0]]:
distance[next[0]] = cost
# ์ฐ์ ์์ํ์ ๊ฑฐ๋ฆฌ์ ๋
ธ๋ ์ ๋ณด ์ ์ฅ
heapq.heappush(queue, (cost, next[0]))
return
# V: ์ ์ ์ ๊ฐ์, E: ๊ฐ์ ์ ๊ฐ์, start: ์ถ๋ฐ์ง์
V, E = map(int, input().split())
start = int(input())
# distance: ์ต๋จ๊ฑฐ๋ฆฌ ํ์ ๋ฐฐ์ด (์ถฉ๋ถํ ํฐ ๊ฐ์ผ๋ก ์ด๊ธฐํ)
distance = [float('INF') for _ in range(V + 1)]
# graph: ์ธ์ ๋ฆฌ์คํธ๋ก ๋ํ๋ธ ๊ทธ๋ํ
graph = [[] for _ in range(V + 1)]
for _ in range(E):
node1, node2, weight = map(int, input().split())
graph[node1].append((node2, weight))
# ์ถ๋ฐ์ง์ ์ผ๋ก๋ถํฐ ๋ค์ต์คํธ๋ผ ํจ์ ์ํ
dijkstra(start)
# ์ต๋จ๊ฑฐ๋ฆฌ ํ
์ด๋ธ ์ถ๋ ฅ
print(distance)
'โญ Personal_Study > Algorithm' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
Segment Tree (0) | 2022.12.03 |
---|---|
[์๊ณ ๋ฆฌ์ฆ] ์ต์ ์ ์ฅ ํธ๋ฆฌ (MST) (1) | 2022.09.29 |
[์๊ณ ๋ฆฌ์ฆ] Union-Find (1) | 2022.09.28 |
๋๊ธ