저희는 그래프 단원에서 가중치 그래프에 대해 짧막하게 소개하고 넘어갔습니다. 요약하자면, 가중치 그래프는 아래와 같이 그래프에 각 간선(edge) 마다 가중치(weight)를 추가한 것입니다. 예를 들어 A에서 B로 가는 데 3의 비용이 든다고 생각하면 됩니다.
이렇게 가중치를 설정하면, 다음과 같은 점을 생각할 수 있습니다.
A에서 D로 가는 경로 중 가장 비용이 작게 드는 경로는 뭘까?
가중치가 없는 그래프에서는 모든 그래프의 가중치가 같았기 때문에 A→B→E→D로 가는 경로나 A→B→C→D로 가는 경로의 비용이 같았습니다. 그러나 가중치 그래프에서는 A→B→E→D로 가는 경로가 더 효율적입니다. 왜냐면 총 비용이 3+5+3=11로 3+8+2=13 보다 작기 때문입니다. 이러한 문제를 해결하기 위해 다익스트라 알고리즘을 사용할 수 있습니다.
다익스트라 알고리즘은 가중치 그래프에서 시작점과 도착점이 주어졌을 때, 최소 비용을 return하는 알고리즘입니다.
다익스트라의 원리
다음과 같이 그래프가 주어지고 시작점은 A, 도착점은 H라 합시다.
1.
각각의 점에 라벨을 매겨 줄 것입니다. 시작점의 라벨은 0으로 초기화하고, 나머지 점들은 로 초기화 합니다.
2.
사용 안 한 라벨 중 제일 작은 라벨을 찾고, 해당 라벨을 사용했다고 표시해줍니다.
3.
해당 점에 인접한 점들의 라벨들을 업데이트 해줍니다. (이미 라벨 되어 있는 값보다 작으면 그 값으로 업데이트 해주고, 크면 업데이트 하지 않습니다.)
2-3의 과정을 반복 합니다.
4.
모든 라벨을 사용했으면 종료합니다.
위 과정이 진행되는 과정을 자세히 보도록 합시다.
다익스트라의 진행
1.
시작 점 A 라벨은 0으로 초기화
2.
나머지 라벨은 로 초기화
1.
사용 안 한 라벨 중에서 가장 작은 것은?
⇒
2.
사용 처리, 인접 점의 라벨 업데이트
1.
사용 안 한 라벨 중에서 가장 작은 것은?
⇒
2.
사용 처리, 인접 점의 라벨 업데이트
1.
사용 안 한 라벨 중에서 가장 작은 것은?
⇒
2.
사용 처리, 인접 점의 라업데데
1.
사용 안 한 라벨 중에서 가장 작은 것은?
⇒
2.
사용 처리, 인접 점의 라벨 업데이트
업데이트 할 라벨 x
1.
사용 안 한 라벨 중에서 가장 작은 것은?
⇒
2.
사용 처리, 인접 점의 라벨 업데이트
1.
사용 안 한 라벨 중에서 가장 작은 것은?
⇒
2.
사용 처리, 인접 점의 라벨 업데이트
업데이트할 라벨 x
1.
사용 안 한 라벨 중에서 가장 작은 것은?
⇒
2.
사용 처리, 인접 점의 라벨 업데이트
업데이트할 라벨 x
1.
사용 안 한 라벨 중에서 가장 작은 것은?
⇒
2.
사용 처리, 인접 점의 라벨 업데이트
업데이트할 라벨 x
모든 라벨들이 업데이트 되었으므로, 이제 알고리즘은 종료됩니다. 각 라벨들은 A에서 해당 점을 가기 위한 최소 비용입니다. 예를 들어, A에서 H로 가기 위한 최소 비용은 5인 것입니다.
이제 다익스트라 알고리즘의 진행을 알아보았으니, 구현을 해보도록 합시다.
다익스트라 구현 (nossi)
1.
그래프 구현
graph = {
"A": [("B", 2), ("D", 1)],
"B": [("C", 2), ("E", 2), ("F", 4)],
"C": [("F", 4)],
"D": [("G", 5)],
"E": [("H", 1)],
"F": [("E", 3)],
"G": [("F", 7), ("H", 6)],
"H": [],
}
Python
복사
2.
distance 구현
INF = int(1e9)
num_v = len(graph)
distance = [INF] * (num_v + 1)
Python
복사
3.
heap 구현
distance[start] = 0
Python
복사
다익스트라의 구현
우선 각 점의 최소 비용을 저장할 list가 필요합니다. 위의 진행 과정처럼, 시작점은 0으로, 다른 모든 점들을 로 라벨을 해줍니다.
distance = [float("inf")] * (vertex + 1)
distance[start] = 0
Python
복사
또한 탐색할 그래프는 삼중 리스트로 되어있다고 가정을 해봅시다. 예를 들어 2번째 index에는 2번 점과 연결된 [점1, 가중치1], [점2, 가중치2], [점3, 가중치3] 으로 저장되어 있습니다.
앞선 진행 과정에서 다음과 같은 질문이 있었습니다
“사용 안 한 라벨 중에서 가장 작은 것은?”
이 접근을 사용하기 위해서는 전에 배운 heap이라는 자료구조를 사용할 것입니다. 특히 min heap을 말이죠. 위의 질문은 이제 아래와 같이 변환할 겁니다.
q = []
heappush(q, [0, start])
Python
복사
“heap에 있는 라벨 중에서 가장 작은 것은?”
heap을 선언 한 후 heappop()을 사용할 것입니다. heappop()을 사용하게 되면, 우선순위(여기서는 라벨)가 제일 작은 원소가 튀어나오기 때문입니다. 그리고 heap이 비어있게 될 때까지 이 과정들을 반복합니다. 일련의 과정은 graph에서의 bfs와 상당히 유사합니다.
while q:
dist, now = heappop(q)
Python
복사
만약 heap에서 나온 가중치가 distance에 이미 저장되어 있는 값보다 크면, 인접 점들을 업데이트 해줄 필요가 없습니다.
while q:
dist, now = heappop(q)
if distance[now] < dist:
continue
Python
복사
이제 인접 점들을 업데이트 하는 부분입니다. 현재 비용에 인접 점의 가중치를 더한 값이 distance에 있는 값보다 작으면 업데이트 해주고 heap에 넣어줍니다. 이 과정을 모든 인접 점들에 대해 해줍니다.
while q:
dist, now = heappop(q)
if distance[now] < dist:
continue
for vv, ww in graph[now]:
cost = distance[now] + ww
if cost < distance[vv]:
distance[vv] = cost
heapq.heappush(q, (cost, vv))
Python
복사
heap이 비어있게 되면, 더 이상 업데이트 할 수가 없어, 알고리즘이 종료 됩니다. return은 요구사항에 맞게 써주면 됩니다. 여기서는 start에서 end까지의 거리(비용)을 return하겠습니다.
return distance[end]
Python
복사
모든 과정들을 합친 코드는 아래에 있습니다. bfs와 heap의 개념이 잘 잡혀있고, 다익스트라의 구현 과정을 이해했으면 코드에 대한 설명은 어렵지 않을 것입니다. 그럼에도 보는 것과 코드를 직접 짜는 것은 다른 문제임으로, 여러 번 코드를 짜보고 즉각즉각 나오도록 하는 것이 좋겠습니다.
from heapq import heappop, heappush
def dijkstra(graph, start, end):
distance = [float("inf")] * (vertex + 1)
distance[start] = 0
q = []
heapq.heappush(q, (0, start))
while q:
dist, now = heapq.heappop(q)
if distance[now] < dist:
continue
for vv, ww in graph[now]:
cost = distance[now] + ww
if cost < distance[vv]:
distance[vv] = cost
heapq.heappush(q, (cost, vv))
return distance[end]
Python
복사
Copyright 2023. 노씨데브. All rights reserved. 무단 공유 및 배포를 금합니다.