다익스트라(Dijkstra) 알고리즘

들어가기전에..

그래프 탐색 기반 경로 계획

• 지점들과 각 지점 사이의 비용을 각각 노드(Node)와 간선(Edge)를 통해 그래프 구조로 표현
  

그래프 구조

• 각 단위의 정보들을 연결하여 구조화시킨 자료 구조
  • 노드(Node) : 각 이동 지점
  • 간선(Edge) : 노드 간의 연결
• 출발 노드부터 목표 노드 사이에 통과하는 간선 상의 가중치, 즉 소요되는 비용의 합을 최소화하는 경로를 탐색

최소 비용 문제

1. 다익스트라(Dijkstra) 알고리즘

1.1 다익스트라 알고리즘이란?

• 그래프의 한 노드에서 나머지 노드까지의 최소 비용을 구하는 알고리즘
• 단, 이때 음의 간선을 포함할수 없음

• 활용분야
  • 구글 맵스 및 교통 경로 시스템
  • 컴퓨터 네트워크의 라우팅 경로
  • 산업 공학의 최소 운송비 지점 등

1.2 알고리즘 순서

1. 출발 노드로부터 각 노드까지의 최소 비용을 저장할 배열과 방문 여부를 초기화
   • 이때, 각 노드까지의 최소비용은 $\infty$(무한대)로 설정한다.(이론상 최대의 값 또는 아주 큰값)
2. 출발 노드의 비용과 방문 여부를 각각0과 "방문"으로 갱신한다.

3. 현재 노드와 간선이 연결된 인접 노드까지의 최소 비용을 갱신한다. 각 인접 노드에 대해 다음의 값을 비교한다.
   (1) : (현재 노드까지의 최소비용) + (현재 노드에서 인접 노드까지의 비용)
   (2) : (인접 노드까지의 비용)
   (3) : (1)과 (2)의 값을 비교하여 (1)의 값이 (2)보다 작은 경우(비용이 더 작은 경우), (1)의 비용으로 (2)의 비용을 갱신

4. 현재 노드에 인접한 모든 노드에 대해 비용을 비교하여, 필요 시 갱신한다. 인접한 모든 노드에 방문 후, 방문 상태를 "완료"로 갱신한다.

5. 아직 방문하지 않은 노드들 중, 비용이 가장 적은 노드를 방문하여 3~4 단계를 수행한다.

6. 모든 노드를 방문할때까지 위의 과정을 반복

1.3 예제 문제

• 출발 노드(Start) : A
• 도착 노드(Goal) : G

1. 초기화

• 모든 노드에 대해 INF(무한대)로 초기화

2. 노드 A

• 출발 노드(A)부터 탐색 시작
  • 출발 노드의 비용을 0으로 갱신
• 인접한 노드 B, C, E 에 대해 비용 갱신
• 노드 A의 방문상태를 '방문'으로 갱신

3. 노드 B

• 미방문 노드 중, 비용이 가장 작은 노드 B 방문
• 인접한 노드 C, D의 기존 경로와 새로운 경로의 비용을 비교 및 필요시 갱신
  • 노드 C
    • 기존 경로 : A -> C 의 비용 : 6
    • 새로운 경로 : A -> B -> C 의 비용 : 5
      C의 비용을 더작은 비용인 5로 갱신

4. 노드 C

• 인접한 노드 D, F, G에 대해 비용 비교 및 갱신
  • 노드 D
    • 기존 경로 : A -> B -> D 의 비용 : 8
    • 새로운 경로 : A -> B -> C -> D 의 비용 : 7
      D의 비용을 더 작은 비용인 7로 갱신

5. 노드 D

• 인접한 노드 G에 대해 비용 비교 및 갱신
  • 노드 G
    • 기존 경로 : A -> B -> C -> G 의 비용 : 10
    • 새로운 경로 : A -> B -> C -> D 의 비용 : 8
      G의 비용을 더 작은 비용인 8로 갱신

나머지 노드 E, F에 대해서도 동일하게 적용시키면 다음과 같은 결과가 나온다.

6. 최종경로

• A -> B -> C -> D -> G 총 비용 8

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

• 최적성 보장
  • 모든 노드를 방문하여 최소 비용 경로를 탐색하기 때문에, 시작 노드에서 목표 노드까지 경로의 최적성을 보장

• 구현의 용이성
  • 상대적으로 알고리즘에 대한 이해과 구현이 용이

• 연산 시간
  • 노드의 수와 연결 경로가 증가함에 따라 방문해야 하는 경로의 개수가 급격히 증가
  • 노드와 연결 경로가 많은 대규모의 그래프 구조에서 경로를 계획해야 하는 경우, 최소 비용 경로를 도출하기 위해 많은 시간이 필요

3. 연습문제

• 시작 노드(Start) : A
• 목표 노드(Goal) : I

최종 경로

• A(0) -> B(3) -> C(5) -> F(9) -> I(11) 총 비용 11

4. 다익스트라 알고리즘 코드

import heapq
import matplotlib.pyplot as plt

def dijkstra(graph, start_node, end_node):
    # 각 노드까지의 거리를 무한대로 초기화
    distances = {node : float('inf') for node in graph}
    # 각 노드의 방문 여부를 False로 초기화
    visited = {node : False for node in graph}
    # 각 노드의 이전 노드를 저장할 딕셔너리를 None으로 초기화
    predecessors = {node : None for node in graph}
        
    # 시작 노드까지의 거리는 0으로 설정
    distances[start_node] = 0

    # 우선순위 큐를 초기화하고 시작 노드를 추가
    pq = [(0, start_node)]

    # 우선순위 큐가 빌 때까지 반복
    while pq:
        # 우선순위 큐에서 가장 작은 거리의 노드를 꺼냄
        current_distance, current_node = heapq.heappop(pq)

        # 이미 방문한 노드인 경우 스킵
        if visited[current_node]:
            continue
    
        # 현재 노드를 방문 처리
        visited[current_node] = True

        # 목표 노드에 도달한 경우, 최단 경로를 구하고 반환
        if current_node == end_node:
            path = []
            while current_node:
                path.append(current_node)
                current_node = predecessors[current_node]
            path.reverse()
            return path, distances[end_node]
        
        # 현재 노드와 이웃한 노드들을 확인하며 최단 거리 갱신
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight

            # 새로운 거리가 기존의 거리보다 짧은 경우 갱신
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                predecessors[neighbor] = current_node
                heapq.heappush(pq, (distance, neighbor))

    # 목표 노드에 도달할 수 없는 경우 None 반환
    return None, None

# 주어진 그래프 정의
graph = {
    'A' : {'B' : 3, 'C' : 6, 'E' : 7},
    'B' : {'A' : 3, 'C' : 2, 'D' : 5},
    'C' : {'A' : 6, 'B' : 2, 'D' : 2, 'E' : 5, 'F' : 4, 'G' : 6},
    'D' : {'B' : 5, 'C' : 2, 'G' : 1},
    'E' : {'A' : 7, 'C' : 5, 'F' : 3, 'H' : 2},
    'F' : {'C' : 4, 'E' : 3, 'G' : 3, 'H' : 2, 'I' : 2},
    'H' : {'E' : 2, 'F' : 2, 'I' : 7},
    'G' : {'C' : 5, 'D' : 1, 'F' : 3, 'I' : 6},
    'I' : {'F' : 2, 'G' : 6, 'H' :7}
}

# 각 노드의 위치 지정
# 각 노드의 위치 지정
pos = {
    'A': (0, 0),
    'B': (1, 1),
    'C': (1, -1),
    'D': (2, 1),
    'E': (2, -1),
    'F': (3, 0),
    'G': (3, 2),
    'H': (4, -1),
    'I': (4, 1)
}

# 시작 노드와 목표 노드 설정
start_node = 'A'
end_node = 'E'

# 다익스트라 알고리즘을 사용하여 최단 경로와 최단 거리 계산
path, shortest_distance = dijkstra(graph, start_node, end_node)

# 최단 경로 및 최단 거리 출력
print(f"The shortest path from {start_node} to {end_node} is : {path}")
print(f"The shortest distance is : {shortest_distance}")

# 그래프 그리기
plt.figure(figsize=(8, 6))

# 간선 그리기
for node in graph:
    for neighbor, weight in graph[node].items():
        plt.plot([pos[node][0], pos[neighbor][0]], [pos[node][1], pos[neighbor][1]], 'k-')

# 노드 그리기
# 노드 그리기
for node in graph:
    plt.plot(pos[node][0], pos[node][1], 'o', markersize=10, alpha=0.5)
    plt.text(pos[node][0], pos[node][1], node, fontsize=12, ha='center', va='center')

plt.axis('off')
plt.show()

실행 결과

The shortest path from A to I is : ['A', 'B', 'C', 'F', 'I']
The shortest distance is : 11