[파이썬][알고리즘] 최단 경로 알고리즘

최단 경로 알고리즘

최단 경로 문제

• 두 노드를 잇는 최단 경로 찾는 문제
• 가중치 그래프에서 가중치 합이 최소가 되는 것을 찾는 문제

문제 종류

1. 단일 출발 및 단일 도착 문제
   • 특정 노드 2개를 선택 후 가장 짧은 경로를 찾는 문제
2. 단일 출발 문제
   • 특정 노드 1개에서 다른 노드들 간 가장 짧은 경로를 찾는 문제
3. 전체 쌍 문제
   • 그래프 내 노드 쌍에 대한 최단 경로를 찾는 문제

다익스트라 알고리즘

• 단일 출발에 대한 답을 찾는 문제
• 첫 노드를 기준으로 인접한 노드를 추가해 가면서 최단 거리를 구해나가는 방법
  • 너비 우선 탐색과 유사
• 우선순위 큐를 이용

1) 첫 노드를 기준으로 각 노드들 간의 거리를 저장하는 배열 생성

• 첫 노드의 거리는 0, 나머지는 무한대로 설정 (inf)
• 첫 정점 거리 (0)을 먼저 배열에 입력한다.

2) 우선순위 큐에서 노드를 꺼냄

• 첫 노드에 인접한 노드들에 대해 각 노드로 가는 거리와 현재 배열에 저장되어 있는 값과 비교하여 거리가 짧을 경우 업데이트
• 업데이트가 된 경우 우선순위 큐에 입력

3) 업데이트될 노드가 없을 때까지 반복

단계

1. 초기화
   • 첫 노드를 기준으로 거리 저장
     • 첫 노드는 0, 나머지는 inf

2. 인접한 노드와의 거리 계산

   • 우선순위 큐에서 노드를 꺼냄
   • 인접한 노드들과의 거리 비교 후 더 짧을 경우 업데이트

3. 우선순위 큐의 가장 앞에 있는 노드 정보를 가지고 이 노드와 인접 노드 간의 거리 비교

• A-C-B의 거리가 A-B의 거리보다 짧기 때문에 업데이트
• A-D의 거리가 A-C-D보다 짧기 때문에 그대로 둔다

 

4. 마지막 노드 D에서 인접한 노드까지의 거리 계산

5. 인접 노드가 없으면 우선순위 큐에서 pop을 하고 그다음에 들어있는 데이터를 이용하여 위 과정을 반복한다.

코드 구현

import heapq

queue = []
heapq.heappush(queue, [3, 'A'])
heapq.heappush(queue, [7, 'B'])
heapq.heappush(queue, [1, 'C'])
heapq.heappush(queue, [11, 'D'])
print(queue)

[[1, 'C'], [7, 'B'], [3, 'A'], [11, 'D']]

graph = {
    'A': {'B':8, 'C':2, 'D':3},
    'B':{},
    'C':{'B':3, 'D':2},
    'D':{'E':1, 'F':4},
    'E':{},
    'F':{}
}

import heapq

def dijkstra(graph, first):
    distance = {node:float('inf') for node in graph}
    distance[first] = 0 # 첫 번째 노드거리 0    
    queue = []
    heapq.heappush(queue, [distance[first], first]) # 우선순위 큐에 첫번째 값 넣어줌

    # queue에 데이터 없을 때 까지 반복
    while queue:
        current_distance, current_node = heapq.heappop(queue)

        if distance[current_node] < current_distance: # 우선순위 큐의 값이 더 클경우 반복문 실행할 필요 없음
            continue

        for next_node, weight in graph[current_node].items():
            total_distance = current_distance + weight

            if total_distance < distance[next_node]:
                distance[next_node] = total_distance
                heapq.heappush(queue, [total_distance, next_node])

    return distance

dijkstra(graph, 'A')

{'A': 0, 'B': 5, 'C': 2, 'D': 3, 'E': 4, 'F': 7}

시간 복잡도

• 두 가지 과정을 거침
  • 각 노드의 인접한 노드를 비교
  • 우선순위 큐에 정보를 넣고 삭제하는 과정
• 각 과정별 복잡도
  • 모든 노드를 비교하는 과정 : O(E)
  • 노드를 비교할 때마다 배열을 업데이트하고 우선순위 큐에 데이터를 넣었을 때
    • 간선마다 한 번씩 일어나므로 최대 O(E)
    • 우선순위 큐에서 MiniHeap을 구성하는데 걸리는 시간 O(logE)
    • 따라서 시간 복잡도는 O(ElogE)
• 총 시간 복잡도: O(E) + O(ElogE) = O(ElogE)

최단 경로 찾기

import heapq

def dijkstra(graph, first, last):
    distance = {node:[float('inf'), first] for node in graph}
    distance[first] = [0, first]
    queue = []

    heapq.heappush(queue, [distance[first][0], first])

    while queue:
        current_distance, current_node = heapq.heappop(queue)

        if distance[current_node][0] < current_distance:
            continue

        for next_node, weight in graph[current_node].items():
            total_distance = current_distance + weight

            if total_distance < distance[next_node][0]:
                # 다음 노드까지 총 거리와 어떤 노드를 통해서 왔는지 입력
                distance[next_node] = [total_distance, current_node]
                heapq.heappush(queue, [total_distance, next_node])
    # 마지막 노드부터 첫번째 노드까지 순서대로 출력
    path = last
    path_output = last + '->'
    while distance[path][1] != first:
        path_output += distance[path][1] + '->'
        path = distance[path][1]
    path_output += first
    print(path_output)
    return distance

dijkstra(graph, 'A', 'F')

F->D->A





{'A': [0, 'A'],
 'B': [5, 'C'],
 'C': [2, 'A'],
 'D': [3, 'A'],
 'E': [4, 'D'],
 'F': [7, 'D']}