시작점 A에서 각 노드별 최소거리 구하는 방법
결과:
{‘A’: 0, ‘B’: 6, ‘C’: 1, ‘D’: 2, ‘E’: 5, ‘F’: 6}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
import heapq
graph = {
'A':{'B':8, 'C':1, 'D':2},
'B': {},
'C': {'B':5, 'D':2},
'D': {'E':3, 'F':5},
'E': {'F':1},
'F': {'A':5}
}
# start에 'A'가 들어감.ㅎ
def dij(graph, start):
# distance array 생성
distances = { node : float('inf') for node in graph }
print("distances : "+str(distances))
# 시작노드-시작노드 거리는 0 !
distances[start] = 0
# heapq 이용해서 p-queue 생성. queue에는 아래와 같이 들어가 있음. {숫자:노드이름}
queue = []
heapq.heappush(queue, [distances[start], start])
print(queue)
while queue:
# p-queue 에서 가장 작은 거리부터 하나씩 꺼낸다. ㅎ
cur_distance, cur_node = heapq.heappop(queue)
print(cur_distance, cur_node)
#만약,, distnace 에 저장된 애보다 크면 continue.ㅋ
if cur_distance > distances[cur_node]:
continue
#이제 현재 노드 기준으로 for 순회
for node, weight in graph[cur_node].items():
print(node, weight)
# cur_node에서 이 노드까지의 거리(가중치) 계산
distance = cur_distance + weight
print("distance : "+str(distance))
# 만약.. 현재 노드의 거리보다 새로 계산된 거리가 더 짧을 경우.
if distances[node] > distance:
# 현재 노드의 거리에 업뎃 하고
distances[node] = distance
# ★중요★ 그런 경우에는 추가 확인이 필요하므로 해당노드와 거리를 p-queue에 넣어줌.
heapq.heappush(queue, [distance, node])
print(distances)
dij(graph, 'A')