Advanced Algorithm - 최단경로(Shortest Path) 알고리즘(2)

* 해당 포스팅은 최단경로(Shortest Path) 알고리즘(1)과 이어지는 내용입니다.

 

1. 파이썬을 이용한 다익스트라 알고리즘 구현(우선순위 큐 활용) 

 

a) heapq 라이브러리를 활용하여 우선순위 큐 사용하기

# heapq 라이브러리를 이용한 우선순위 큐 작성

import heapq

queue = []

# heappush(자료구조, 삽입할 데이터) - queue라는 자료구조에 MinHeap 형태로 데이터를 삽입한다. 
# 거리를 key로 노드명을 value로 사용한다.
heapq.heappush(queue, [2,'A'])
heapq.heappush(queue, [5,'B'])
heapq.heappush(queue, [1,'C'])
heapq.heappush(queue, [7,'D'])

 

 

[테스트 및 결과 검증] 

 

 

b) 다익스트라 알고리즘 구현

 

 

- 위의 그래프를 딕셔너리를 이용하여 구현한다. 

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}
}

 

 

 

- 다익스트라 알고리즘을 구현한다. 

import heapq

def dijikstra(graph, start): # 그래프와 시작노드를 매개변수로 받는다.
    
    # node:float = node가 갖는 키는 그대로 사용하고 값(value)을 무한으로 설정한다.
    # for node in graph = 그래프의 노드개수만큼 딕셔너리를 만든다.    
    distances = {node:float('inf') for node in graph}
    distances[start] = 0 # 시작 노드값은 0으로 초기화한다. 
    queue = [] # 우선순위 큐로 사용할 리스트  
    
    # distance[start] = 거리(key), start = 노드이름(value)
    heapq.heappush(queue,[distances[start], start])
    
    # 우선순위 큐에 데이터가 있는 동안 명령수행
    while queue:
        
        # 우선순위 큐에 들어있는 값을 뽑아낸다.
        current_distance, current_node = heapq.heappop(queue) 
        
        # 해당 노드에 대해 배열에 들어있는 최단거리가 
        # 우선순위 큐에서 뽑아온 최단거리보다 작은 경우, 계산 필요없음  
        if distances[current_node] < current_distance:
            continue
        
        # 우선순위 큐에서 뽑아온 값을 가지고 그래프의 인접노드와 가중치를 알아낸다.
        for adjacent, weight in graph[current_node].items():
            distance = current_distance + weight #인접노드를 가기위한 거리계산
            
            # 현재 최단거리로 갖고 인접노드(adjacent)의 거리값(distances[adjacent])이
            # 방금 우선순위 큐에서 뽑아와서 계산한 인접노드의 거리값(distance)보다 크다면
            if distance < distances[adjacent]:
                distances[adjacent] = distance # 해당 노드의 최단거리를 업데이트한다.
                heapq.heappush(queue, [distance, adjacent])
                
    return distances

 

 

 

[실행 결과]

 

 

c) 참고자료 - 최단 경로 및 거쳐야 하는 노드를 함께 출력해주는 메소드 

import heapq

# 탐색할 그래프와 시작 정점을 인수로 전달받습니다.
def dijkstra(graph, start, end):
    # 시작 정점에서 각 정점까지의 거리를 저장할 딕셔너리를 생성하고, 무한대(inf)로 초기화합니다.
    distances = {vertex: [float('inf'), start] for vertex in graph}

    # 그래프의 시작 정점의 거리는 0으로 초기화 해줌
    distances[start] = [0, start]

    # 모든 정점이 저장될 큐를 생성합니다.
    queue = []

    # 그래프의 시작 정점과 시작 정점의 거리(0)을 최소힙에 넣어줌
    heapq.heappush(queue, [distances[start][0], start])

    while queue:
        
        # 큐에서 정점을 하나씩 꺼내 인접한 정점들의 가중치를 모두 확인하여 업데이트합니다.
        current_distance, current_vertex = heapq.heappop(queue)
        
        # 더 짧은 경로가 있다면 무시한다.
        if distances[current_vertex][0] < current_distance:
            continue
            
        for adjacent, weight in graph[current_vertex].items():
            distance = current_distance + weight
            # 만약 시작 정점에서 인접 정점으로 바로 가는 것보다 현재 정점을 통해 가는 것이 더 가까울 경우에는
            if distance < distances[adjacent][0]:
                # 거리를 업데이트합니다.
                distances[adjacent] = [distance, current_vertex]
                heapq.heappush(queue, [distance, adjacent])
    
    path = end
    path_output = end + '->'
    while distances[path][1] != start:
        path_output += distances[path][1] + '->'
        path = distances[path][1]
    path_output += start
    print (path_output)
    return distances

# 방향 그래프
mygraph = {
    'A': {'B': 8, 'C': 1, 'D': 2},
    'B': {},
    'C': {'B': 5, 'D': 2},
    'D': {'E': 3, 'F': 5},
    'E': {'F': 1},
    'F': {'A': 5}
}

print(dijkstra(mygraph, 'A', 'F'))

 

 

 

[실행 결과]

 

 

[결과를 읽는 방법]

ex) 'B' : [6, 'C'] = A에서 B를 가기위해 C를 거치는것이 최단경로이며 거리는 6이다. 

 

---

2. 다익스트라 알고리즘의 시간복잡도

a) 다익스트라 알고리즘은 크게 2가지 과정을 거친다.

• 과정 1) 각 노드마다 인접한 간선들을 모두 검사하는 과정
• 과정 2) 우선순위 큐에서 노드&거리 정보를 넣고(push) 삭제(pop)하는 과정

b) 각 과정별 시간복잡도

• 과정 1) 첫 노드와 다른 노드간의 접근경로가 모두 존재하는 경우, 각 노드는 최대 1번씩 방문하게 되어있다. 그러므로 경로 최대치는 간선의 수 이상이 될 수 없다. 즉, 모든 간선은 최대 1번씩 검사되며 이는 각 노드마다 인접한 간선들을 모두 검사하는 과정으로 O(E) 만큼의 시간이 걸린다. E는 간선(Edge)을 의미한다. 
• 과정 2) 매 순간 비교를 할 때마다 배열과 우선순위 큐의 노드&거리 정보가 계속해서 갱신되는 경우, 최대 O(E)만큼의 시간이 걸리고, O(E)개의 노드/거리 정보에 대해 우선순위 큐를 유지하는데 O(E log E) 만큼의 시간이 걸린다. 

 

c) 총 시간 복잡도

• 과정 1 + 과정 2 = O(E) + O(E log E) = O(E log E)
  - 빅 오 표기법은 최대치를 시간복잡도로 잡기 때문에 최종적으로 O(E log E) 만큼의 시간복잡도를 갖는다.

 

* 참고 - 힙의 시간 복잡도

• depth (트리의 높이) 를 h라고 표기한다면,
• n개의 노드를 가지는 heap 에 데이터 삽입 또는 삭제시, 최악의 경우 root 노드에서 leaf 노드까지 비교해야 하므로 h=log2n 에 가까우므로, 시간 복잡도는 O(logn)