[최단경로] 다익스트라 | 백준 1753번 | python

🌟 다익스트라 알고리즘이란?

하나의 시작 정점에서 다르정점까지의 최단 경로를 계산하는 것이다. 
최단 경로 알고리즘이라고도 불린다! 

 

⚒️ Dijkstra의 최단 경로 알고리즘

다음과 같은 그림에서 최단경로를 계산하려고 한다.

 

1. 각 단계에서 S안에 있지 않은 정점 중에서 가장 distance값이 작은 정점을 S에 추가한다.
2. 정점 W를 거쳐서 정점 u로 가는 가상적인 더 짧은 경로가 있다고 가정해보자!
   그러면 정점 v에서 정점 u까지의 거리는 v->w->u (경로2 + 경로3) 거리가 된다.
3. 그러나 경로 2는 경로 1보다 항상 길 수 밖에 없다. 현재 distance 값이 가장 작은 정점은 u이기 때문이다. => 거리1 < 거리2 + 거리3

 

이 알고리즘을 해결하기 위해선 3가지를 고려해야한다. 

• direction
• visited
• queue
• distance

✔️ direction

각 노드의 인접 노드 번호와 거리가 저장되어있는 리스트

 

✔️ visited

노드 방문 여부

 

✔️ queue

1. 우선순위 큐에서 노드 가져오기
2. 현재 선택된 노드를 방문한 적이 있는지 확인
3. 현재 노드를 방문 노드로 업데이트
4. for 현재 노드의 인접 노드 만큼
    4-1. 인접 노드의 distance > 현재 노드의 distance + 인접 노드까지의 거리 이면
    4-2. 인접 노드의 distance 값 변경
    4-3. queue에 인접 노드 추가

 

✔️ distance

시작점으로부터 각 노드까지의 최단 거리 저장 배열

 

---

👾 최단경로 - 백준 1753번

https://www.acmicpc.net/problem/1753

예제 입력1

5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6

예제 출력1

0
2
3
7
INF

 

📍풀이 ⭐️

 

초기 설정

1. visited 초기화
2. 각 노드의 distance는 최대로 

 

distance

[1]	[2]	[3]	[4]	[5]
0	∞	∞	∞	∞

 

direction = [[] for _ in range(V + 1)]
visited = [False] * (V + 1)
queue = PriorityQueue()
distance = [sys.maxsize] * (V + 1)

 

direction 리스트에 다음과 같이 저장한다.

 

1 -> [2,2], [3,3]

2 -> [3,4], [4,5]
3 -> [4,6]
4
5 -> [1,1]

 

for _ in range(E):
    start, end, weight = map(int, input().split())

    direction[start].append([end, weight])
    
# 출력 
# direction [[], [[2, 2], [3, 3]], [[3, 4], [4, 5]], [[4, 6]], [], [[1, 1]]]

 

다익스트라 수행

1️⃣ K를 시작점으로 설정

queue.put((0, K)) 
distance[K] = 0

 

2️⃣ queue가 빌 때까지

(1) 우선순위 큐에서 노드 가져오기
(2) 현재 선택된 노드를 방문한 적이 있는지 확인
(3) 현재 노드를 방문 노드로 업데이트
(4) for 현재 노드의 인접 노드 만큼
      (4.1) 인접 노드의 distance > 현재 노드의 distance + 인접 노드까지의 거리 이면
      (4.2) 인접 노드의 distance 값 변경
      (4.3) queue에 인접 노드 추가

 

 

1번 노드 선택

 

visited

[0]

1

 

distance

[1]	[2]	[3]	[4]	[5]
0	2	3	∞	∞

 

queue

[0]	[1]
2	3

 

2번 노드 선택

visited

[0]	[1]
1	2

 

distance

[1]	[2]	[3]	[4]	[5]
0	2	3	7	∞

 

queue

[0]	[1]
3	4

 

 

3번 노드 선택

 

visited

[0]	[1]	[2]	[3]
1	2	3	4

 

distance

노드4 같은 경우, 기존에 있는 값이 신규 값보다 작을 경우 갱신하지 않음! (7 < 3+6)

[1]	[2]	[3]	[4]	[5]
0	2	3	7	∞

 

queue

[0]

4

 

while queue.qsize() > 0:
    current = queue.get()

    current_node = current[1]

    if visited[current_node]:
        continue

    visited[current_node] = True

    for tmp in direction[current_node]:
        next = tmp[0]
        value = tmp[1]

        if visited[next]:
            continue

        if distance[next] > distance[current_node] + value:  # 더 짧은 distance 갱신
            distance[next] = distance[current_node] + value

            queue.put((distance[next], next))

 

📍전체 코드

# 다익스트라
import sys
from queue import PriorityQueue
input = sys.stdin.readline

# V(정점의 개수), E(간선의 개수)
V, E = map(int, input().split())
# K (시작 정점)
K = int(input())

direction = [[] for _ in range(V + 1)]
visited = [False] * (V + 1)
queue = PriorityQueue()
distance = [sys.maxsize] * (V + 1)

for _ in range(E):
    start, end, weight = map(int, input().split())

    direction[start].append([end, weight])

# print("direction", direction)

queue.put((0, K))  # K를 시작점으로 (거리, 출발)
distance[K] = 0

while queue.qsize() > 0:
    current = queue.get()

    current_node = current[1]

    if visited[current_node]:
        continue

    visited[current_node] = True

    for tmp in direction[current_node]:
        next = tmp[0]
        value = tmp[1]

        if visited[next]:
            continue

        if distance[next] > distance[current_node] + value:  # 더 짧은 distance 갱신
            distance[next] = distance[current_node] + value

            queue.put((distance[next], next))

for i in range(1, V + 1):
    if visited[i]:
        print(distance[i])
    else:
        print("INF")