알고리즘 - 다익스트라 알고리즘

다익스트라 알고리즘

최단경로 알고리즘이란

최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘이다.

최단 경로 문제는 보통 그래프를 이용해 표현하는데 각 지점은 그래프에서 '노드'로 표현되고, 지점 간 연결된 도로는 그래프에서 '간선'으로 표현된다.

 

최단 경로 알고리즘

• BFS
• DiJkstra 알고리즘

 

가중치

다익스트라 알고리즘의 가중치는 경로의 비용(거리, 시간, 요금)이다.

• 항상 0 이상이어야 한다.
  • 다익스트라는 간선의 가중치가 모두 0 또는 양수 일 때만 정상적으로 작동한다.
• 가장 비용이 적게 드는 노드를 선택하여 최단 거리를 확정한다.

 

동작원리

다익스트라 최단경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발해 다른 노드로 가는 각각의 최단 경로를 구하는 알고리즘이다.

 

1. 출발 노드를 설정한다.
2. 최단 거리 테이블을 초기화한다.
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
5. 3번과 4번을 반복한다.

 

결국 가장 짧은 거리의 노드를 찾는 시간을 단축하기 위해 우선순위 큐와 힙을 사용해야 한다.

• 최소 힙
  • 기본 큐는 순차적으로 탐색하지만 최소 힙 기반의 우선순위 큐를 사용하면 가장 짧은 거리의 노드를 적은 시간 복잡도로 꺼낼 수 있다.
• 거리가 짧은 노드부터 먼저 방문하고 거리를 갱신하므로 나중에 더 긴 경로를 찾아도 효율적으로 처리할 수 있다. 

 

BFS와 다익스트라의 차이점

	BFS	다익스트라
간선 가중치	모든 간선 가중치가 동일한	간선마다 가중치가 다름
작동 원리	시작부터 단계별로 인접한 노드를 모두 방문	시작점과 가장 가까운 노드를 우선 방문
자료구조	일반 큐 사용	우선순위 큐 사용

 

 

시간복잡도

우선순위 큐 사용 가정

간선의 수를 E(Edge), 정점의 수를 V(Vertex)라고 했을 때,

1. 각 정점마다 인접한 간선을 모두 조사하려면 각 정점을 1번씩만 방문되므로 O(E)
2. 우선순위 큐에서 간선들을 넣고 빼는 과정은 log(E)
3. 모든 간선을 우선순위 큐에 넣고 뺀다면 O(ElogE)
4. 그래프에서 중복 간선을 포함하지 않는다면 E는 항상 정점의 수 제곱 이하( log E < log(V^2) )
5.  log E < log(V^2) = 2 logV이므로 O(logV)로 나타낼 수 있음
6. 따라서 최종 시간 복잡도는 O(ElogV)

선형탐색

1. 매번 최단 거리를 찾기 위해 V번 탐색
2. 각 노드마다 인접한 간선을 확인하므로 O(V^2+E)
3. 따라서 최종 시간 복잡도는 O(V^2)

 

 

 

---

코드 구현

 

 

다음과 같은 그래프가 있다.

이 그래프로 다익스트라 알고리즘을 구현해보자

파이썬 코드

import heapq

graph = {					# 사진 그래프 입력
    'A' : {'B':4, 'C':1},
    'B' : {'D':2},
    'C' : {'B':2, 'D':6},
    'D' : {}
}

def Dijkstra(graph, start):	# 그래프와 시작 노드를 매개변수로 받음
    distances = {node: float('inf') for node in graph}
    distances[start] = 0	# 최단거리 

    parent_nodes = {node:None for node in graph}
    # 직전 정점을 딕셔너리 형태로 저장 {현재정점 : 직전정점}

    queue = []
    heapq.heappush(queue, (0, start))

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

        if distances[current_node] < current_distance:
            continue

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

            if distance < distances[neighbor]:	# 현재경로보다 주변노드의 경로가 더 짧다면
                distances[neighbor] = distance
                parent_nodes[neighbor] = current_node	# 직정 정점을 갱신
                heapq.heappush(queue, (distance, neighbor))
                
    return distances, parent_nodes

# 경로 복원하는 함수
def Dijkstra_path(parent_nodes, start, target):
    path = []
    current = target
	
    while current is not None:		
        path.append(current)
        current = parent_nodes[current]

    path.reverse()			# 역순으로 담겼으므로 뒤집음

    if path[0] == start:	
        return "->".join(path)
    return "경로 없음"		# if문에 걸리지 않았다는 건 출발점이 일치하지 않음(경로없음)




start_node = 'A'			# 시작 노드 A
distances, parent_nodes = Dijkstra(graph, start_node)

print("==== A에서 출발하는 다익스트라 ====")
for node in graph:
    dist = distances[node]
    path_str = Dijkstra_path(parent_nodes, start_node, node)
    print(f"목적지[{node}], 최단거리: {dist}, 이동경로: {path_str}")

 

출력결과

 

시작 시점을 C로 설정하면 이런 출력결과가 나온다