최단 경로와 관련된 문제를 풀어보다가 bfs만으로는 해결이 안되는 문제가 있었다. 인터넷을 찾아보니 bfs가 아닌 다익스트라 알고리즘 혹은 플로이드 워셜 알고리즘으로 푼 사람들이 많았다. 이 둘다 모르는 나에게는 애시당초 풀 수 없는 문제였다. 그래서 다익스트라와 플로이드 위셜을 공부한 후에 풀어보기로 했다. 이 글에서는 다익스트라에 대해서 글을 쓰겠다.
- 다익스트라
다익스트라 알고리즘은 다이나믹 프로그래밍을 활용한 최단경로 알고리즘이다. 최초의 다익스트라는 도형에서 두 꼭짓점 간의 최단경로를 찾는 알고리즘이라 한다. 하지만 변형되어 한 꼭짓점(소스라 함)을 기준으로 다른 모든 꼭짓점까지의 최단경로를 찾는 알고리즘이 됬다고 한다. 변형된 알고리즘에 대해서 공부하기로 했다.
이 알고리즘이 다이나믹 프로그래밍인 이유는 "최단거리는 여러개의 최단거리로 이루어져있기 때문이다." 라고 한다. 작동방식은
- 출발노드와 도착노드를 설정
- 모든 노드 간에 거리 값을 부여
- 출발노드에서 방문하지 않은 인접노드를 방문, 거리를 계산하여 현재 알고 있는 거리보다 짧다면 거리 값을 갱신
- 현재 노드에서 인접한 모든 미방문 노드의 거리를 계산했다면 현재 노드는 방문했으므로 미방문 노드의 집합에서 제거
- 도착노드가 미방문 노드에서 벗어나면 알고리즘 종료라고 한다. 이 과정에서 방문하지 않은 인접노드를 저장할 때 우선순위 큐라는 자료구조를 사용한다고 한다. python에서는 이를 구현하기 위해 heapq을 사용한다.
- Code
예시로 만들어본 그래프이다. A노드를 기준으로 B노드로 가는 길은 많지만 최단경로는 A->B 혹은 A->D->B이다. 그 경로의 값은 3이다. C의 경우에는 B로가는 어떠한 경우보다 A->F->E->C가 최단경로이다.
import heapq
graph = {'A': {'B': 6, 'D': 2, 'F': 3},
'B': {'A': 3, 'C': 4, 'D': 1},
'C': {'B': 4, 'E': 1, 'F': 5},
'D': {'A': 2, 'B': 1, 'F': 2, 'G': 8},
'E': {'C': 1, 'F': 1},
'F': {'A': 3, 'E': 1, 'G': 1},
'G': {'D': 8, 'F': 1}}
def dijkstra(graph, start_node):
dists = {node: float('inf') for node in graph} # 각 노드까지의 최소 거리를 저장하기 위한 변수
dists[start_node] = 0 # 자기자신의 최소 거리는 0
queue = []
heapq.heappush(queue, [start_node, dists[start_node]]) # 시작노드부터 탐색하기 위해 지정
while queue:
now_node, now_dist = heapq.heappop(queue)
if now_dist > dists[now_node]: # 현재 노드까지 최소 거리가 지금거리보다 짧다면 비교할 필요 X
continue
for new_node, new_dist in graph[now_node].items():
dist = new_dist + now_dist
if dist < dists[new_node]:
dists[new_node] = dist
heapq.heappush(queue, [new_node, dist])
return dists
print(dijkstra(graph, 'A'))
출력
{'A': 0, 'B': 3, 'C': 5, 'D': 2, 'E': 4, 'F': 3, 'G': 4}- 단점
다익스트라는 최소 거리를 구할 수 있지만 한가지 단점이 존재한다고 한다. 그것은 바로 음수가 존재해서는 안된다고 한다.
위와 같은 그래프가 있다고 가정하고 생각해보겠다.
1) A를 시작노드라고 가정하면 dists = [0, ∞, ∞]가 된다.
2) A->B로 가게 되면 dists = [0, 20, ∞]가 된다.
3) A->C로 가게 되면 dists = [0, 20, 10]이 된다.
4) dists에서 가장 거리가 짧은 C노드로 가게 된다.
5) C를 방문하게 되면 C가 갱신될 상황이 없어서 A->C는 10으로 마무리된다.
하지만 실질적으로는 A->B->C가 -1로 최솟값을 갖는다. 이러한 문제로 음수일 때 다익스트라는 최소거리를 구할 수 없다고 한다. 이를 해결하기 위해 플로이드 워셜이라는 알고리즘이 있다고 한다.
