다익스트라(dijkstra)

다익스트라는 그리디(Greedy)를 활용한 최단 경로(Shortest Path) 탐색 알고리즘이다(one to all)

다익스트라 알고리즘은 음의 간선을 포함할 수 없음

음수 간선이 있으면, 이미 처리된 노드의 거리보다 더 짧은 경로가 나중에 발견되는 경우가 발생할 수 있으므로 다익스트라의 정확성이 보장되지 않는다

음수 사이클 탐지 기능 없음

그리디 알고리즘(Greedy Algorithm)이란?

• 지금 이 순간 가장 최적인 선택을 하는 것 전체 최적해(global optimum)를 보장하진 않지만, 특정 조건을 만족할 경우 빠르고 간단하게 접근하는 방식

코드 리뷰

import heapq

# 그래프 초기화 (인접 리스트)
from collections import defaultdict

def dijkstra(start, graph, V):
    # 거리를 무한대로 초기화
    INF = float('inf')
    distance = [INF] * (V + 1)
    distance[start] = 0  # 시작 정점은 거리 0

    # 최소 힙(우선순위 큐) 사용
    pq = []
    heapq.heappush(pq, (0, start))  # (거리, 정점)

    while pq:
        dist, now = heapq.heappop(pq)

        # 이미 더 짧은 거리로 방문한 적이 있으면 무시
        if distance[now] < dist:
            continue

        # 현재 노드와 연결된 이웃 노드들 확인
        for neighbor, cost in graph[now]:
            new_cost = dist + cost
            if new_cost < distance[neighbor]:
                distance[neighbor] = new_cost
                heapq.heappush(pq, (new_cost, neighbor))

    return distance

# 정점 수와 간선 정보
V = 6  # 정점 개수

# (출발 정점, 도착 정점, 가중치)
edges = [
    (1, 2, 2),
    (1, 3, 5),
    (2, 3, 3),
    (2, 4, 4),
    (3, 4, 1),
    (4, 5, 1),
    (5, 6, 2)
]

graph = defaultdict(list)

for u, v, w in edges:
    graph[u].append((v, w))
    # 방향 그래프가 아닐 경우 아래 줄도 추가
    # graph[v].append((u, w))

# 다익스트라 실행
start = 1
distances = dijkstra(start, graph, V)

# 결과 출력
print(f"[{start}]번 정점에서의 최단 거리:")
for i in range(1, V + 1):
    if distances[i] == float('inf'):
        print(f"{i}: 도달 불가")
    else:
        print(f"{i}: {distances[i]}")

1. 시작 정점을 기준으로 ‘dist[]’ 초기화
2. 우선순위 큐에서 현재까지 최단 거리인 정점 u를 꺼냄
3. 해당 정점의 인접 노드를 모두 확인하면서 ‘dist[v] = dist[u] + cost(u, v)’로 갱신
4. 방문 처리된 노드는 재처리하지 않음 -> ‘dist[u]’는 확정된 최단 거리

시간 복잡도

구현 방식	시간 복잡도
인접 리스트 + 힙	O(E log V)
인접 행렬 + 선형 검색	O(V²)

E : 간선 수
V : 정점 수