Graph: Dijkstra 다익스트라 - 최단 경로 찾기 문제

✅ 1. Dijkstra 알고리즘이란?

• 가중치가 있는 그래프에서 **최단 경로(가장 비용이 적은 경로)**를 구할 때 사용하는 알고리즘이에요.
• **BFS(너비 우선 탐색)**은 모든 간선의 가중치가 1일 때만 최단 경로를 찾을 수 있어요. 하지만 Dijkstra는 가중치가 다를 때도 최단 경로를 보장해줘요.

---

✅ 2. 왜 BFS로는 안 될까?

• 예: edges = [[A,B], [A,C], [B,D], [C,B], [C,D], [C,E], [D,E]]
• 이건 가중치 없는 그래프라서 BFS로 A → D 최단 경로를 구할 수 있어요.
• 하지만 가중치가 달라지면 BFS는 "몇 개의 노드를 지나느냐"만 고려하기 때문에 최단 경로가 아닐 수 있어요.

---

✅ 3. Dijkstra 알고리즘의 핵심 원리

• **Greedy 알고리즘(탐욕 알고리즘)**의 일종으로, 매 단계마다 가장 비용이 적은 경로를 선택해요.
• 한 번 방문한 노드도 더 짧은 경로가 발견되면 다시 방문할 수 있어요.
• 가중치가 음수면 사용하면 안 돼요!

---

✅ 4. 예시 그래프 (가중치 포함)

python

복사편집

edges = [ [A, B, 10], [A, C, 3], [B, D, 2], [C, B, 4], [C, D, 8], [C, E, 2], [D, E, 5] ]

📍 A에서 시작해서 모든 노드까지의 최단 경로를 구한다면?

노드최단 경로비용

노드	최단경로	비용
A	A	0
B	A → C → B	7
C	A → C	3
D	A → C → B → D	9
E	A → C → E	5

---

✅ 5. Dijkstra 알고리즘의 작동 방식 (요약)

1. 각 노드의 최단 거리를 저장할 shortest 딕셔너리를 만들어요. (초기엔 무한대)
2. 시작 노드 A는 거리 0으로 시작.
3. **min-heap(최소 힙)**에 (거리, 노드)를 넣고 시작.
4. 힙에서 가장 작은 거리의 노드를 꺼내고,
5. 그 노드의 이웃 노드들을 확인하면서,
6. 현재 노드를 통해 도달하는 것이 기존보다 더 짧다면 업데이트하고 힙에 넣어요.
7. 힙이 빌 때까지 반복.

---

✅ 6. 핵심 자료구조

• adj: 인접 리스트, 각 노드가 어디와 연결되어 있는지와 가중치를 저장.
• shortest: 각 노드까지의 최소 거리 저장.
• heapq: Python에서 제공하는 우선순위 큐 (최소 힙 구현).

---

✅ 7. 핵심 아이디어

• 매 순간 가장 비용이 적은 경로만 선택하면서 전체 최적 해를 찾아가는 구조.
• BFS는 "방문했냐/안 했냐"만 보지만,
• Dijkstra는 "더 짧은 경로로 다시 갈 수 있냐?"를 계속 따져요.

import heapq  # heapq는 우선순위 큐(최소 힙)를 구현하는 모듈입니다.

# edges: 간선 정보가 담긴 리스트 [(출발노드, 도착노드, 가중치), ...]
# n: 노드의 개수 (노드는 1번부터 n번까지 존재한다고 가정)
# src: 시작 노드 (최단 경로를 구할 출발점)
def shortestPath(edges, n, src):
    adj = {}  # 인접 리스트(adjacent list)를 저장할 딕셔너리

    # 모든 노드를 키로 갖는 빈 리스트 생성 (노드 번호는 1부터 n까지)
    for i in range(1, n + 1):
        adj[i] = []
        
    # 인접 리스트 채우기: 각 노드에 대해 연결된 노드와 가중치를 저장
    for s, d, w in edges:
        adj[s].append([d, w])  # 예: adj[1] = [[2, 5], [3, 10]] => 1번에서 2번(가중치5), 3번(가중치10)으로 연결

    shortest = {}  # 각 노드까지의 최단 거리 저장 (확정된 노드만 담음)
    minHeap = [[0, src]]  # 최소 힙: [현재까지 누적 가중치, 노드] 형태로 시작 노드를 0의 거리로 초기화

    # 힙이 빌 때까지 반복
    while minHeap:
        w1, n1 = heapq.heappop(minHeap)  # 가장 누적 가중치가 작은 노드를 꺼냄

        if n1 in shortest:
            continue  # 이미 최단 거리가 확정된 노드는 무시

        shortest[n1] = w1  # 현재 노드까지의 최단 거리 확정

        # 현재 노드와 연결된 이웃 노드들 확인
        for n2, w2 in adj[n1]:
            if n2 not in shortest:
                # 아직 최단 거리가 확정되지 않은 노드는 힙에 추가
                # 누적 거리 = 현재까지 거리(w1) + 이웃 노드까지 거리(w2)
                heapq.heappush(minHeap, [w1 + w2, n2])

    return shortest  # 모든 노드에 대한 최단 거리 딕셔너리 반환

 

https://youtu.be/XEb7_z5dG3c?si=VQdE9E8PelB1EsWQ

 

class Solution:
    def shortestPath(self, n: int, edges: List[List[int]], src: int) -> Dict[int, int]:
        # 인접
        adj = {} # adj[src] = [[dst, weight]]
        for i in range(n): # n : 노드 개수
            adj[i] = []

        # s=src, d=dst, w=weight
        for s, d, w in edges:
            adj[s].append([d,w])

        # comput shortest paths
        shortest = {}
        minheap = [[0, src]] # 초기값은 src, 가중치를 0으로

        while minheap: # 힙에 데이터가 있을때만
            w1, n1 = heapq.heappop(minheap)
            # min heap 이어서, 가중치가 적은 값이 먼저 pop 되서 
            # shortest 에 들어가므로
            # 나중에 pop 되는 노드는 그냥 넘어가면됨
            if n1 in shortest: 
                continue
            
            shortest[n1] = w1

            # n1에서 갈수있는 dst 들 검색
            for n2, w2 in adj[n1]:
                # 새로운 노드(도착지, dst)가 최단. 에 없으면
                if n2 not in shortest: 
                    # 최단 값에 넣어줌
                    heapq.heappush(minheap, [w1+w2, n2])

        # Note: If a vertex is unreachable from the source vertex, 
        #       the shortest path distance for the unreachable vertex should be -1.
        #       정점에서 소스 정점에 도달할 수 없는 경우, 
        #       도달할 수 없는 정점의 최단 경로 거리는 -1이어야 합니다.
        
        # Fill in missing nodes
        for i in range(n):
            # 위 로직이 완료됬는데, shortest 에 노드가 없으면
            # 도달할 수 없는 노드라는 의미니깐.
            if i not in shortest:
                shortest[i] = -1 # -1로 세팅

        return shortest