[TIL] 최단 경로 알고리즘 - 다익스트라

최단 경로란?

• 두 노드를 잇는 가장 짧은 경로를 찾는 것
• 가중치 그래프에서 간선의 가중치 합이 최소가 되도록 하는 경로

1. 특정 노드에서 출발하여 또 다른 특정노드에 도착하는 가장 짧은 경로를 찾음
2. 그래프 내의 특정 노드에 대해 다른 모든 노드 각각에 대한 가장 짧은 경로를 찾음 ex) 다익스트라
3. 그래프 내의 모든 쌍에 대한 최단 경로를 찾음

 

다익스트라 알고리즘

• 최단 경로 알고리즘 중 하나로 하나의 정점에서 다른 모든 정점 간의 각각 가장 짧은 거리를 구하는 알고리즘
• 인접한 정점들의 거리를 계산하여 최단 거리로 갱신
• BFS와 비슷

 

다익스트라 알고리즘 이해

• 우선순위 큐를 사용 (최소힙) -> 가장 낮은 우선순위를 가진 노드를 pop
• 각 정점까지의 거리를 계산하는 배열과 인접노드와 그 거리를 비교하는 우선순위 큐 두가지를 활용

그래프와 다익스트라 알고리즘 구현 예시

 

위 사진은 그래프와 다익스트라 알고리즘을 구현하는 로직을 그려본 것이다.

순서대로 정리해보면

 

* 빨간 화살표는 우선순위큐에서 팝하는 요소를 가리킨다.

1. 왼쪽은 정점들의 최단 거리를 저장하는 배열, 오른쪽 큐는 인접 정점을 저장하는 우선순위 큐이다.

2. 초기에는 가장 첫번째 정점인 A의 거리를 0으로 하고 나머지를 무한대(inf)로 저장한다.

3. 우선 순위 큐에 첫 번째 정점 A와 A의 거리를 담고 인접 정점들의 거리를 업데이트한다. 

    그리고 우선순위 큐에 업데이트된 정점들을 가중치 순으로 저장한다.

4. (C,1)에서 D까지 최단거리가 6이므로 D의 거리를 업데이트하고 (D,6)을 우선순위 큐에 저장한다.

5. 우선순위 큐의 (B,2)에서 B->C까지의 거리는 3이지만 거리 배열에 저장된 1(A->C)이 더 작으므로 업데이트 하지 않는다.

6. 이후의 모든 과정이 5번과 마찬가지로 동작한다.

7. 최종적으로 정잠 A에서부터 모든 정점까지의 최단거리 배열은 [0,2,1,6,4]가 된다.

 

 

다익스트라 알고리즘 구현

• 우선순위 큐의 구현을 위해 파이썬의 heapq 라이브러리 활용
• 탐색할 그래프와 시작 정점을 인수로 전달받는 함수를 만듦

import heapq


def dijkstra(graph, start, end):	# start: 시작 정점, end: 끝 정점

    #거리 배열 초기화
    dist = {vt: [float('inf'), start] for vt in graph}
    dist[start] = [0, start]
    q = []
    
    #우선순위큐 초기화
    heapq.heqppush(q, [dist[start][0], start])
    
    while q:
    	cur_dist, cur_vt = heapq.heappop(q)
        
        # 거리 배열의 저장되어 있는 경로가 더 짧다면 무시
        if dist[cur_vt][0] < cur_dist:
        	continue
		
        for adj, weight in graph[cur_vt].items():
            new_dist = cur_dist + weight

            # 짧은 경로로 거리 업데이트, 최단 거리도 구할 것이므로 지나가는 정점으로 업데이트
            if new_dist < dist[adj][0]:
                dist[adj] = [new_dist, cur_vt]
                heapq.heappush(q, [new_dist, adj])

    path = end
    path_out = end + '->'
    while dist[path][1] != start:
        path_out += dist[path][1] + '->'
        path = dist[path][1]
    path_out += start
    print(path_out)			# E->A (최단거리)
  
    return dist
    
    
graph={
    'A':{'B':2, 'C':1, 'E':4},
    'B':{'C':3},
    'C':{'D':5},
    'D':{'E':1},
    'E':{},
}

print(dijkstra(graph, 'A', 'E'))	# {'A': [0, 'A'], 'B': [2, 'A'], 'C': [1, 'A'], 'D': [6, 'C'], 'E': [4, 'A']}

 

 

다익스트라 알고리즘의 시간복잡도?
- 노드마다 인접 간선 검사 -> O(E) 
- 우선순위 큐에 가장 많은 노드의 삽입/삭제가 이루어지는 경우 -> O(ElogE)
결과적으로 O(ElogE)
*E = edge