자료구조와 알고리즘 - 다익스크라(Dijkstra algorithm)

 

---

 

 

다익스트라(Dijkstra) 알고리즘은 그래프에서 한 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이다. 주로 가중치가 있는 그래프에서 사용되며 가중치의 값은 음수이면 안된다.(방향그래프, 무방향 그래프 둘 다 적용 가능)

 

 

 

 다음과 같은 단방향 그래프가 있고 각 숫자는 두 정점의 소요되는 시간을 의미한다.이때 A에서 출발하여 모든 정점에 도달하는 최소시간을 구하고자 할 때 다익스트라 알고리즘을 활용할 수 있다.

그래프

 

 다익스트라 알고리즘은 시작 정점에서부터 출발하여, 시작 정점과 가장 가까운 정점을 선택하고 이를 통해 다른 정점들과의 최단 거리를 계산한다. 계산된 최단 거리는 점차적으로 업데이트되며, 더 짧은 거리를 찾을 때마다 최신화된다.

 

다익스트라는 두가지 과정을 반복한다.

 

1. 최소값 업데이트

2. 시작 정점과 가장 가까운 정점으로 이동 및 방문 처리

 

이때 중요한 점은 탐색의 우선순위가 시작 정점과 가장 가까운 정점이라는 것이다.

예를 들어서

A => B 는 7

A => C는 12 일때

B로 가는 경로의 시간이 짧으므로 B부터 탐색한다.

 

---

 

- 과정

자세한 과정은 다음과 같다.

 

 

 

 

 

 

- 파이썬 코드

# 행: 출발지 (A B C D E F 순)
# 열: 목적지 (A B C D E F 순)

INF = float("inf")
#방향 그래프
graph = [
    [0,7,12,INF,INF,INF],
    [INF,0,2,9,INF,INF],
    [INF,INF,0,INF,10,INF],
    [INF,INF,INF,0,INF,1],
    [INF,INF,INF,4,0,5],
    [INF,INF,INF,INF,INF,INF]
]

# #무방향
# graph = [
#     [0,7,12,INF,INF,INF],
#     [7,0,2,9,INF,INF],
#     [12,2,0,INF,10,INF],
#     [INF,9,INF,0,4,1],
#     [INF,INF,10,4,0,5],
#     [INF,INF,INF,1,5,0]
# ]

# 배열에서 가장 작은 값 찾는 함수
def get_smallest_value_index(distances,visited):

    min_value = INF
    
    min_value_index = 0
    
    for i in range(len(distances)):

        if not visited[i] and distances[i] < min_value : # 해당 노드를 방문하지 않고 최소값을 지닌 노드
            min_value = distances[i]
            min_value_index = i
    
    if min_value == INF: #모두 순회를 했는데 만약 최소값이 INF면 더이상 갈 곳이 없다는 뜻
        
        return -1
    
    else:

        return min_value_index



def dijkstra(start_node):
    visited = [False]*6 #방문노드 처리
    distances = graph[start_node][:] #시작노드의 거리 정보 가져오기
    visited[start_node] = True #시작노드를 방문처리
    
    while True:
        
        next_node = get_smallest_value_index(distances,visited) #다음 갈곳을 정한다.
        visited[next_node] = True #방문처리한다.

        if next_node == -1:  #더 이상 갈곳이 없으면 멈춘다.
            break
        
        cost = distances[next_node] #출발지에서 해당노드에 가기위한 비용을 가져온다.

        for i in range(len(distances)):
            
            if not visited[i]: 
                
                new_cost = cost + graph[next_node][i] #해당노드에 도달할때 비용 + 그 다음 노드에 갈 때 비용

                if new_cost < distances[i]: #테이블 값보다 작으면 업데이트
                    distances[i] = new_cost

    return distances           

# 예시로 0번 노드(A)에서 시작하는 다익스트라 알고리즘 실행
print(dijkstra(0))

 

 

 

- 다익스트라 알고리즘 최적화

 

 배열에서 가장 작은 값을 찾을 때 선형 탐색을 하였지만 이를 우선순위 큐를 활용하면 최적화를 할 수 있다.

 

 다익스트라 알고리즘에서 간선의 개수를 E, 정점의 개수를 V라고 할 때, 출발지에서 가장 가까운 정점을 찾는 과정을 배열을 사용하여 단순 탐색하는 경우, 각 단계에서 모든 정점을 확인해야 하므로 O(V)의 시간이 소요된다. 알고리즘은 모든 정점을 한 번씩 방문하므로, 이 과정을 V번 반복한다. 따라서 정점 선택에 O(V^2)의 시간이 걸리고, 각 정점에 대해 모든 간선을 검사해야 하므로, 간선 검사에 O(E)의 시간이 추가로 소요된다. 결과적으로 배열을 사용한 다익스트라 알고리즘의 전체 시간 복잡도는 O(V^2 + E)이다.

 하지만 우선순위 큐를 사용하면 가장 가까운 정점을 선택하는 데 O(log V)의 시간이 걸리며, 이 과정을 모든 정점에 대해 수행하므로 정점 선택에 총 O(V log V)의 시간이 소요된다. 각 정점에 대해 모든 인접 간선을 검사하는 과정은 여전히 O(E)의 시간이 걸리지만, 각 간선은 우선순위 큐에 한 번씩만 추가되므로, 간선 검사에 드는 총 시간은 O(E log V)이다. 따라서 우선순위 큐를 사용한 다익스트라 알고리즘의 전체 시간 복잡도는 O((V + E) log V)이다.

 

import heapq

INF = float("inf")

graph = [
    [0, 7, 12, INF, INF, INF],
    [INF, 0, 2, 9, INF, INF],
    [INF, INF, 0, INF, 10, INF],
    [INF, INF, INF, 0, INF, 1],
    [INF, INF, INF, 4, 0, 5],
    [INF, INF, INF, INF, INF, INF]
]

def dijkstra(start_node):
    visited = [False] * len(graph)  # 방문노드 처리
    distances = [INF] * len(graph)  # 거리 정보를 무한대로 초기화
    distances[start_node] = 0  # 시작 노드의 거리는 0으로 설정
    queue = []
    
    # 시작 노드를 우선순위 큐에 추가 (거리, 노드 인덱스)
    heapq.heappush(queue, (0, start_node))
    
    while queue:
        current_distance, current_node = heapq.heappop(queue)
        
        # 이미 방문한 노드는 무시
        if visited[current_node]:
            continue
        
        visited[current_node] = True
        
        for neighbor in range(len(graph[current_node])):
            distance = graph[current_node][neighbor]
            if distance != INF and not visited[neighbor]:
                new_distance = current_distance + distance
                if new_distance < distances[neighbor]:
                    distances[neighbor] = new_distance
                    heapq.heappush(queue, (new_distance, neighbor))
    
    return distances

# 예시로 0번 노드(A)에서 시작하는 다익스트라 알고리즘 실행
print(dijkstra(0))

 

 

 

- 관련 문제

https://www.acmicpc.net/problem/1238

1238번: 파티

 

https://www.acmicpc.net/problem/4485

4485번: 녹색 옷 입은 애가 젤다지?