simple_dijkstra (๊ฐ๋จํ ๋ค์ต์คํธ๋ผ)
- ์ฌ๋ฌ ๋ ธ๋๊ฐ ์์ ๋, ์ธก์ ํ ๋ ธ๋์์ ์ถ๋ฐํ์ฌ ๋ค๋ฅธ ๋ ธ๋๋ก ๊ฐ๋ ๊ฐ๊ฐ์ ์ต๋จ๊ฒฝ๋ก๋ฅผ ๊ตฌํด์ฃผ๋ ์๊ณ ๋ฆฌ์ฆ (์์ ๊ฐ์ )์ด ์์๋ ์ ์์ ์ผ๋ก ์๋ํ๋ค. ๊ทธ๋์ ํ์ค์ธ๊ณ์ ๊ธธ์ ํ ๋๋ก gps๋ฑ์ ์ฃผ๋ก ์ฐ์ด๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค.
- ๊ธฐ๋ณธ์ ์ผ๋ก ๊ฐ์ฅ ๋น์ฉ์ด ์ ์ ๋ ธ๋๋ฅผ ์ฐพ์ ๊ฐฑ์ ํ๋ฏ๋ก ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ์ผ๋ก ๋ถ๋ฅ๋๋ค
์๊ณ ๋ฆฌ์ฆ์ ์๋ฆฌ๋ก๋
- ์ถ๋ฐ ๋ ธ๋๋ฅผ ์ค์
- ์ต๋จ ๊ฑฐ๋ฆฌ ํ ์ด๋ธ์ ์ด๊ธฐํ
- ๋ฐฉ๋ฌธํ์ง ์์ ๋ ธ๋ ์ค์์ ์ต๋จ๊ฑฐ๋ฆฌ๊ฐ ๊ฐ์ฅ ์งง์ ๋ ธ๋๋ฅผ ์ ํ
- ํด๋น ๋ ธ๋๋ฅผ ๊ฑฐ์ณ ๋ค๋ฅธ ๋ ธ๋๋ก ๊ฐ๋ ๋น์ฉ์ ๊ณ์ฐํ์ฌ ์ต๋จ ๊ฑฐ๋ฆฌ ํ ์ด๋ธ ๊ฐฑ์
- ์ ๊ณผ์ ์์ 3๊ณผ 4๋ฅผ ๋ฐ๋ณต
ํ๋จ๊ณ๋ฅผ ์๋ฃํ๋ฉด ๊ทธ ๋จ๊ณ์ ๋ ธ๋๋ ์ต๋จ๊ฑฐ๋ฆฌ๊ฐ ํ์คํ ๊ตฌํด์ง๊ฒ์ด๋ค.
๊ฐ๋จํ ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ O(v^2)์ ์๊ฐ๋ณต์ก๋๋ฅผ ๊ฐ์ง๋๋ฐ ์ด๋ v๋ ๋ ธ๋์ ๊ฐ์์ด๋ค.
๋ค์ต์คํธ๋ผ๋ ์ต๋จ ๊ฒฝ๋ก๋ฅผ ๊ตฌํ๋ ์๊ณ ๋ฆฌ์ฆ์ด์ง๋ง ๋ณดํต ์ฝ๋ฉํ ์คํธ์์๋ ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ์๊ตฌํ๋ฏ๋ก ์ต๋จ ๊ฑฐ๋ฆฌ๋ ๊ตฌํ๋ ์๊ณ ๋ฆฌ์ฆ์ ๊ณต๋ถํ๋ค.
import sys
input = sys.stdin.readline # ์
๋ ฅ๋ฐ์ดํฐ๊ฐ ๋ง๋ค๋ ๊ฐ์ ํ์ ๋น ๋ฅธ ์
๋ ฅ์ ๋ฐ๋ ๋ด์ฅํจ์ ์ฌ์ฉ
INF = int(1e9) #๋ฌดํ์ ๋ํ๋ด๋ ๊ฐ์ผ๋ก 10์ต ์ค์
n, m = map(int, input().split()) #๋
ธ๋์ ๊ฐ์, ๊ฐ์ ์ ๊ฐ์
start = int(input()) # ์์ ๋
ธ๋๋ฒํธ
graph = [[] for i in range(n + 1)] # ๊ฐ ๋
ธ๋์ ์ฐ๊ฒฐ๋์ด ์๋ ๋
ธ๋์ ๋ํ ์ ๋ณด๋ฅผ ๋ด๋ ๋ฆฌ์คํธ
visited = [False] * (n + 1) # ๋ฐฉ๋ฌธํ ์ ์ด ์๋์ง ์ฒดํฌํ๋ ๋ชฉ์ ์ ๋ฆฌ์คํธ ๋ง๋ค๊ธฐ
distance = [INF] * (n + 1) # ์ต๋จ ๊ฑฐ๋ฆฌ ํ
์ด๋ธ์ ๋ชจ๋ ๋ฌดํ๋๋ก ์ด๊ธฐํ
for _ in range(m): # ๋
ธ๋๋ค ์ฌ์ด์ ์ฐ๊ฒฐ ์ ๋ฌด์ ๊ฐ์ ์ ๋น์ฉ ์
๋ ฅ
a, b, c = map(int, input().split())
graph[a].append((b,c)) # a๋ฒ ๋
ธ๋์์ b๋ฒ ๋
ธ๋๋ก ๊ฐ๋๋น์ฉ์ด c๋ผ๋ ์๋ฏธ
def get_smallest_node(): # ๋ฐฉ๋ฌธํ์ง ์์ ๋
ธ๋ ์ค์์, ๊ฐ์ฅ ์ต๋จ๊ฑฐ๋ฆฌ๊ฐ ์งง์ ๋
ธ๋์ ๋ฒํธ ๋ฐํ
min_value = INF
index = 0 # ๊ฐ์ฅ ์ต๋จ๊ฑฐ๋ฆฌ๊ฐ ์งง์ ๋
ธ๋(์ธ๋ฑ์ค)
for i in range(1, n + 1):
if distance[i] < min_value and not visited[i]: # ๋ง์ฝ distance[i] < INF์ด๊ณ visited๊ฐ True์ด๋ฉด
min_value = distance[i]
index = i
return index
def dijkstra(start):
distance[start] = 0
visited[start] = True
for j in graph[start]: # j[0] = ๋
ธ๋, j[1] = ๋น์ฉ (์ฆ start์ ์ฐ๊ฒฐ๋ ๋
ธ๋(distance[๋
ธ๋])์ ๋น์ฉ์ ์
๋ฐ์ดํธ)
distance[j[0]] = j[1]
for i in range(n - 1): # ์์๋
ธ๋๋ฅผ ์ ์ธํ n-1๊ฐ์ ๋
ธ๋์ ๋ํด ๋ฐ๋ณต
now = get_smallest_node() # ํ์ฌ ์ต๋จ ๊ฑฐ๋ฆฌ๊ฐ ๊ฐ์ฅ ์งง์ ๋
ธ๋๋ฅผ ๊บผ๋ด์ด
visited[now] = True # ๋ฐฉ๋ฌธ์ฒ๋ฆฌ False -> True
for j in graph[now]: # ํ์ฌ ๋
ธ๋์ ์ฐ๊ฒฐ๋ ๋ค๋ฅธ ๋
ธ๋๋ฅผ ํ์ธ
cost = distance[now] + j[1]
if cost < distance[j[0]]: # ํ์ฌ ๋
ธ๋๋ฅผ ๊ฑฐ์ณ์ ๋ค๋ฅธ ๋
ธ๋๋ก ์ด๋ํ๋ ๊ฑฐ๋ฆฌ๊ฐ ๋ ์งง์ ๊ฒฝ์ฐ ์ฒ๋ฆฌ
distance[j[0]] = cost
dijkstra(start) # ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ ์คํ
for i in range(1, n + 1): # ๋ชจ๋ ๋
ธ๋๋ก ๊ฐ๊ธฐ์ํ ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ์ถ๋ ฅ
if distance[i] == INF: # ๋๋ฌ ๋ถ๊ฐ๋ฅ ํ ๊ฒฝ์ฐ ๋ฌดํ๋ ์ถ๋ ฅ
print('INFINITY')
else: # ๋๋ฌ ๊ฐ๋ฅํ ๊ฒฝ์ฐ ๊ฑฐ๋ฆฌ ์ถ๋ ฅ
print(distance[i])
'์ฝ๋ฉํ ์คํธ > ๊ธฐ๋ณธ ์๊ณ ๋ฆฌ์ฆ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
์ต๋จ๊ฑฐ๋ฆฌ (improved_dijkstra) (0) | 2022.02.24 |
---|---|
์ต๋จ๊ฑฐ๋ฆฌ (Floyd_Warshall) (0) | 2022.02.23 |
๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ(Dynamic_Programming) (0) | 2022.02.20 |
์์ฐจํ์(Sequential_Search) (0) | 2022.02.20 |
์ด์งํ์(Binary_Search) (0) | 2022.02.20 |