[Coding Test][Python][Shortest Path] Dijkstra Algorithm(다익스트라) 개념 및 예제

Coding Test

[Coding Test][Python][Shortest Path] Dijkstra Algorithm(다익스트라) 개념 및 예제

어떻게든 되겠지~ 2025. 1. 30. 19:13

1. Dijkstra Algorithm 이란?

Dijkstra 알고리즘이란 Weighted Graph에서 시작점과 도착점이 주어졌을 때 최단 경로(Shortest Path)를 찾는 알고리즘이다.

시작 Node에서 출발하여 각 Node 까지의 최단 거리를 점진적으로 갱신하며 계산한다. 탐색은 "이미 방문한 Node"와 "방문하지 않은 Node"를 구분하여 진행되며, 방문한 Node로 가는 경로 중에서 가장 짧은 경로를 선택해 나간다.

알고리즘 동작 과정

1) Adjance List & Priority Queue 사용

Priority Queue에 시작 Node 추가
우선 순위가 가장 높은(Distrance가 가작 작은) Node 추출
방문 여부 확인
Distance Update
현재 Node에 연결된 Node를 Priority Queue에 추가
목적지에 기록된 Distance 반환

2) Adjancency Matrix

시작점 설정 : 시작 Node의 거리는 0으로 설정하고, 다른 모든 Node의 거리는 Infinity로 설정
탐색 시작 : 시작 Node를 포함한 집합에서, 아직 방문하지 않은 노드 중에서 가장 작은 거리 값을 가진 Node 선택
인접 Node 거리 갱신 : 선택한 Node를 기준으로 인접한 Node의 거리를 갱신
방문 처리 : 현재 Node를 방문 처리하고 2, 3 단계를 반복
종료 : 모든 Node가 방문되었거나, 더 이상 갱신할 거리가 없는 경우 종료

시간 복잡도

Adjacency Matrix 사용할 경우 : $O(V^2)$
Adjacency List와 우선순위 큐를 사용할 경우 : $O((V+E) * log V)$
Vertex의 개수가 적고 Edge의 수가 많으면 Adjacency Matrix가 효율적( $ E \approx V^2$ 일때)
Vertex의 개수가 많고 Edge의 수가 적으면 Priority Queue가 효율적 ( $ E \ll V^2$ 일때)

2. Dijkstra Algorithm 구현

1) Graph 생성(Adjacency List, Adjacency Matrix)

# (weitght, next_node)
V = 8 
INF = float('inf')  # 무한대 값 설정

graph = {
    1: [(2, 2), (1, 4)],
    2: [(1, 3), (9, 5), (6, 6)],
    3: [(4, 6)],
    4: [(3, 3), (5, 7)],
    5: [(1, 8)],
    6: [(3, 5)],
    7: [(7, 6), (9, 8)],
    8: [],
}

adj_matrix = [[INF] * (V+1) for _ in range(V+1)]

for u, dist_list in graph.items():
    for dist, v in dist_list:
        adj_matrix[u][v] = dist

2-1) Dijkstra Algorithm 구현(Adjacency List & Priority Queue 사용, **$O((V+E) * log V)$**)

import heapq

def dijkstra(start_node):
    distances = {}
    # 1. 시작 Node를 Priority Queue에 추가
    pq = [(0, start_node)]
    heapq.heapify(pq)

    while pq:
    	# 2. 우선 순위가 높은(Distance)가 가장 작은 Node 추출
        curr_dist, curr_node = heapq.heappop(pq)
		
        # 3. 방문 여부 확인
        if curr_node not in distances:
        	# 4. 비용 Update
            distances[curr_node] = curr_dist
            # 5. 현재 Node와 연결된 Node를 Priority Queue에 추가
            for next_dist, next_node in graph[curr_node]:
                total_dist = distances[curr_node] + next_dist
                heapq.heappush(pq, (total_dist, next_node))

    return distances
    
start_node = 1
distances = dijkstra(start_node)
print("Shortest distances from node", start_node)
for i in range(1, V+1):
    print(f"Node {i}: {distances[i]}")

Shortest distances from node 1
Node 1: 0
Node 2: 2
Node 3: 3
Node 4: 1
Node 5: 10
Node 6: 7
Node 7: 6
Node 8: 11

2-2) Dijkstra Algorithm 구현(Adjacency Matrix 사용, $O(V^2)$)

def dijkstra(start_node):
    # 1. 시작점 설정
    distances = [INF] * (V+1)
    distances[start_node] = 0
    
    # 방문 여부 배열
    visited = [False] * (V+1)
    
    # 2. 탐색 시작
    # 	 아직 방문하지 않은 노드 중 거리가 가장 작은 Node 선택
    for _ in range(1, V+1):
        min_dist = INF
        current_node = -1
        
        for i in range(1, V+1):
            # 아직 방문하지 않은 노드 중 거리가 가장 작은 Node 선택
            if not visited[i] and distances[i] < min_dist:
                min_dist = distances[i]
                current_node = i

        # 더 이상 방문할 노드가 없으면 종료
        if current_node == -1:
            break 
        
        # 3. 인접 Node 거리 계산
        # 	 curr_node를 기준으로, 인접한 Node들의 거리 갱신
        for next_node in range(1, V+1):
        	# 인접한 Node들
            if adj_matrix[current_node][next_node] != INF:  
                total_dist = distances[current_node] + adj_matrix[current_node][next_node]
                if total_dist < distances[next_node]:
                    distances[next_node] = total_dist
                    
        # 4.현재 노드를 방문 처리
        visited[current_node] = True
        
    return distances

# 시작 노드 1부터 Dijkstra 알고리즘 실행
start_node = 1
distances = dijkstra(start_node)
print("Shortest distances from node", start_node)
for i in range(1, V+1):
    print(f"Node {i}: {distances[i]}")

Shortest distances from node 1
Node 1: 0
Node 2: 2
Node 3: 3
Node 4: 1
Node 5: 10
Node 6: 7
Node 7: 6
Node 8: 11

3. Dijkstra Algorithm 예제

Dijkstra 예제를 풀어보겠습니다. 예제는 Leet Code의 Network Delay Time이란 문제입니다( Network Delay Time - LeetCode )

문제

주어진 네트워크에는 n개의 노드가 있으며 1부터 n까지 Label이 붙어있다.
또한, $times[i]=(u_i, v_i, w_i)$가 주어지는데 $u_i$ 노드에서 신호를 보내서 $v_i$ 노드에 도달하는데 걸리는 시간을 $w_i$라고 한다.
$k$ 노드에서 신호를 보낼 때, 모든 노드에 신호가 도달하기 위한 최소 비용을 구하여라.(하나의 노드에서라도 신호를 받지못하면 -1을 반환하라)

Input & Output

Input : times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2

Output : 2

Constraints

$1 \le k \le n \le 100$
$1 \le time.length \le 6000$
$time[i].length == 3$
$1 \le $u_i, v_i$ \le n $
$1 \le $w_i$ \le 100$
모든 $(u_i, v_i)$ 쌍은 unique

풀이

1) 입력 받기

(Leet code에서는 Input이 주어진 상태로 times를 사용하면 되지만 vscode를 사용하여 풀이하여 input()을 사용하였습니다.)

n, k, e = map(int, input().split(" "))
times = [list(map(int, input().split(" "))) for _ in range(e)]

2) Dijkstra 구현

앞서 본 것과 유사하지만 Start Node를 k로 주어서 Dijkstra Algorithm을 살짝 변형하면 됩니다.

또한 마지막에 방문하지 않은 Node가 존재한다면 -1을 return하면 됩니다.

import heapq
from collections import defaultdict
def dijkstra(times, n, k):
    # Graph 
    # 처음에 element가 없을 때 List를 새로 생성하는 작업들을 생략해준다
    graph = defaultdict(list)
    for u, v, w in times:
        graph[u].append((w, v))

    # Dijkstra 알고리즘
    costs = {}
    pq = []
    heapq.heappush(pq, (0, k))

    while pq:
        curr_cost, curr_node = heapq.heappop(pq)
        if curr_node not in costs:
            costs[curr_node] = curr_cost
            for cost, next_node in graph[curr_node]:
                next_cost = curr_cost + cost
                heapq.heappush(pq, (next_cost, next_node))

    # 방문 못한 노드가 존재한다면 -1 Return
    for node in range(1, n+1):
        if node not in costs:
            return -1

    # 최소값 중에서 최대값 찾기
    return max(costs.values())
    
    
dijkstra(times, n, k)

저작자표시 비영리 변경금지