다익스트라 알고리즘

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

그래프에서 한 정점(시작점)으로부터 다른 모든 정점까지의 최단 거리를 구하는 알고리즘
단, 간선의 가중치는 음수가 없어야 함!

📚 다익스트라라는 이름은?

• 만든 사람: 에츠허르 다익스트라(Edsger W. Dijkstra)
• 네덜란드 출신의 전설적인 컴퓨터 과학자
• 1956년에 고안함! (교통망에서 최단 경로 구할 때 처음 사용)

🚗 알고리즘 아이디어 (쉽게 설명)

네가 서울역에 있다고 가정하 이제 서울역에서 지하철로 가장 빠르게 도착할 수 있는 모든 역까지의 시간을 알고 싶어.

1. 처음엔 자기 자신(시작점)의 거리를 0으로 설정
2. 갈 수 있는 이웃 노드들 중 가장 가까운 노드를 선택
3. 그 노드까지의 거리를 업데이트
4. 이 과정을 반복하면서, 이미 방문한 곳은 다시 방문 안 함

🔧 코드 예시 (Python)

import heapq

def dijkstra(graph, start):
    distance = {node: float('inf') for node in graph}
    distance[start] = 0  # 시작점 거리 0

    queue = [(0, start)]  # (거리, 노드)

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

        # 기존에 더 짧은 경로가 있으면 skip
        if dist > distance[now]:
            continue

        for neighbor, cost in graph[now]:
            new_cost = dist + cost
            if new_cost < distance[neighbor]:
                distance[neighbor] = new_cost
                heapq.heappush(queue, (new_cost, neighbor))

    return distance

📌 사용 예시

graph = {
    'A': [('B', 1), ('C', 4)],
    'B': [('A', 1), ('C', 2)],
    'C': [('A', 4), ('B', 2)],
}

print(dijkstra(graph, 'A'))

🔽 출력 결과:

{'A': 0, 'B': 1, 'C': 3}

✅ 시간 복잡도

• V: 노드 수, E: 간선 수
• O((V + E) log V) (우선순위 큐 사용 시)