[파이썬] [최단경로] 개념 정리 1

1. 방문하지 않은 노드 중 최단거리가 가장 짧은 노드를 선택

2. 해당 노드를 거쳐 다른 노드로 가는 비용과 현재 거리 테이블을 비교하여 갱신

 

1. 다익스트라 알고리즘

• 특정한 노드(출발노드)에서 다른모든 노드로 가는 최단경로를 계산 (음의간선이 없을때)
• 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복한다. (일종의 그리디 알고리즘)
• 동작과정 
  • 출발노드를 설정
  • 최단거리 테이블을 초기화 (자기자신을 제외한 모든노드까지의 거리를 무한대로 설정, 자기자신은 0)
  • 방문하지 않은 노드 중 최단거리가 가장 짧은 노드를 선택 ( 이 과정을 통해 특정 노드까지의 최단거리를 확정짓는것이므로, 모든반복이 끝났을때 전체노드까지의 최단거리가 나오게되는것
  • 해당노드를 거쳐 다른 노드로 가는 비용을 계산해 테이블을 갱신한다
  • 위과정에서 3,4번을 반복한다.
• 최단거리 테이블은 각 노드에 대한 현재까지의 최단거리 정보를 가지고있음
• 처리과정에서 더 짧은경로를 찾으면 "이게 더 짧은 경로야"라고 갱신하는것

 

• 방문하지 않은것중 거리가 짧은것을 선택한다. -> 1번노드를 선택
• 1번노드를 거쳐갈때의 비용 vs 현재비용 (테이블의 비용) 후 짧은것으로 갱신

 

• 2번, 3번, 4번노드의 거리가 갱신됨
• 갱신이 완료되었으므로 다시 반복한다. 거리가 가장 짧은노드인 4번노드를 선택한후 반복 --> 4번노드까지의 최단거리는 이제 더이상 변하지 않는다!! 
• 따라서 4번노드를 거쳐갈때의 최단경로는 현재 4번까지의 최단경로 + 4번에서부터 출발하는 거리 

 

• 이때 4번노드는 이미 방문이 된 노드이므로(=이미 최단거리가 확정된 노드) 건너뛰어도 된다.

마지막노드에 대한 처리는 하지 않아도 됨 -> 이미 최단경로가 모두 결정되었기때문

 

다익스트라 알고리즘의 특징

• 단계를 거치며 한번 처리된 노드의 최단거리는 고정되어 더이상 바뀌지 않음
• 그리디 알고리즘 - 매 상황에서 방문하지 않은 가장 비용이 적은 노드를 선택해 임의의 과정을 반복함
• 한 단계당 하나의 노드에 대한 최단거리를 확실히 찾는것으로 이해할 수 있음

최단 경로 알고리즘

• 가장 짧은 경로를 찾는 알고리즘 → Weighted Graph에서 Edge의 가중치 합이 최소가 되는 경로를 찾는 것이 목적이다.
• 그리디 알고리즘과 다이나믹 프로그래밍 알고리즘이 적용된다.

다익스트라 최단 경로 알고리즘

• 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘
• 매번 최단 거리 테이블을 선형적으로 탐색한다.
• single-source shortest path problem
• 그리디 알고리즘
• 동작 과정
  1. 출발 노드를 설정한다.
  2. 최단 거리 테이블(1차원 리스트)을 초기화한다.
     → 출발 노드에서 다른 모든 노드로 가는 최단 거리를 무한int(1e9)으로 초기화
  3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
  4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
  5. 위 과정에서 3번과 4번을 반복한다.

구현

• 시간복잡도: O(V^2)O(V2)
• dijkstra(initial_node) 내부 for문의 층위를 잘못 설정해서 한참 헤맸다.
• 교재에 나와있는 변수명이 명확하지 않아 조금 수정해보았다.

import sys

input = sys.stdin.readline
INF = int(1e9)

n, m = map(int, input().split())  # 노드, 간선의 수
initial_node = int(input())  # 출발 노드 번호
graph = [[] for i in range(n + 1)]
visited = [False] * (n + 1)
distances = [INF] * (n + 1)

for _ in range(m):
    a, b, c = map(int, input().split())  # c: a와 b 사이의 거리
    graph[a].append((b, c))


def get_node_with_shortest_distance():
    min_value = INF
    index = 0  # 가장 최단 거리가 짧은 노드
    for i in range(1, n + 1):
        if distances[i] < min_value and not visited[i]:
            min_value = distances[i]
            index = i
    return index


def dijkstra(initial_node):
    distances[initial_node] = 0
    visited[initial_node] = True
    for j in graph[initial_node]:
        distances[j[0]] = j[1]
    for i in range(n - 1):
        current_node = get_node_with_shortest_distance()
        visited[current_node] = True
        for j in graph[current_node]:
            distance = distances[current_node] + j[1]
            if distance < distances[j[0]]:
                distances[j[0]] = distance


dijkstra(initial_node)

for i in range(1, n + 1):
    if distances[i] == INF:
        print("INFINITY")
    else:
        print(distances[i])

Input

6 11
1
1 2 2
1 3 5
1 4 1
2 3 3
2 4 2
3 2 3
3 6 5
4 3 3
4 5 1
5 3 1
5 6 2

Output

0
2
3
1
2
4

 

개선된 다익스트라 알고리즘

• 힙 자료구조 사용 → 출발 노드로부터 가장 거리가 짧은 노드를 찾는데 로그 시간이 소요된다. (vs. 다익스트라 알고리즘: O(V)O(V))
  • 파이썬에서는 일반적으로 PriorityQueue보다 heapq가 더 빠르게 동작한다.
  • 파이썬과 자바에서는 기본적으로 Min Heap을 이용하여 우선순위 라이브러리가 구현되어 있다.

구현 1

• 시간복잡도 : O(ElogV)O(ElogV)
• 모든 간선을 힙에 넣었다가 다시 뺀다면 시간복잡도는 O(ElogE)O(ElogE)이다.
• 모든 노드가 연결되어 있을 때 간선의 수는 V^2V2이기 때문에 logElogE는 항상 logV^2logV2보다 작다.
• 따라서 개선된 다익스트라 알고리즘의 시간복잡도는 O(ElogV)O(ElogV)라고 할 수 있다.

import heapq
import sys

input = sys.stdin.readline
INF = int(1e9)

n, m = map(int, input().split())
start = int(input())
graph = [[] for i in range(n + 1)]

distance = [INF] * (n + 1)

for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))


def dijkstra(start):
    queue = []
    heapq.heappush(queue, (0, start))
    distance[start] = 0

    while queue:
        dist, now = heapq.heappop(queue)
        if distance[now] < dist:
            continue
        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(queue, (cost, i[0]))


dijkstra(start)

for i in range(1, n + 1):
    if distance[i] == INF:
        print("INFINITY")
    else:
        print(distance[i])