TIL - 다익스트라(Dijkstra) 최단경로

문제

- 가중치가 음이 아닌(0 이상) 방향 그래프에서, 한 출발점 'start' 에서 다른 모든 정점까지의
  최단 거리를 구하는 표준 알고리즘입니다.
- 1959년 Edsger W. Dijkstra 가 발표하였으며, 우선순위 큐(min-heap) 와 결합한 구현은
  공지된 표준 기법입니다. 본 지문과 테스트 케이스는 본 학습 자료를 위해
  자체적으로 작성되었습니다.

 

 

 

문제풀이

import heapq


INF = float('inf')


def dijkstra(n: int, edges: list, start: int) -> list:
    """
    n: 정점 수 (정점 번호 0 ~ n-1)
    edges: (u, v, w) 형식 방향 간선 리스트
    start: 출발 정점
    반환: 길이 n 의 거리 리스트 (도달 불가 = float('inf'))
    """
    
    # 시작점에서 어딘가에 도달하기 위한 최소값 구하기.
    
    dist = [INF] * n
    dist[start] = 0
    
    # 인접 리스트 구현 (각 인덱스가 하나의 힙이 되도록?)
    graph = [[] for i in range(n)] 
    
    for u,v,w in edges:
        graph[u].append((w,v)) # (거리, 이웃정점)
    
    h = []
    heapq.heappush(h, (dist[start],start))    # 첫 후보 꺼내기 
    
    while h :
        # 힙에서 가장 가까운 후보 꺼내기
        candidate = heapq.heappop(h)
        
        # 정점의 이웃들 전부 추가 
        for i in graph[candidate[1]]:
            # 이웃까지 더 짧은 길이 있으면 dist 갱신, 새 후보 넣기
            neighbor = i
            
            # 이웃점 가중치 = 현재점 가중치 + 가는 가중치
            now_w = dist[candidate[1]]  # 현재점 가중치
            neighbor_w = neighbor[0]    # 가는 가중치 
            new_w = now_w + neighbor_w
            
            if dist[neighbor[1]] > new_w:
                dist[neighbor[1]] = new_w
                new_w_dist = (new_w, i[1])
                
                heapq.heappush(h, new_w_dist)    # 최단거리일때 그 다음값으로 이동 
                  
    return dist

 

 

다익스트라(Dijkstra) 최단경로

특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산한다. 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작한다. (음수 간선이 있을때 쓰는건 벨만-포드) 

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

 

 

다익스트라 최단경로의 개념? 을 Claude 에게 추론을 유도하라고 해서 학습했다. 내가 이해한 바로는, 힙은 최소값을 구하는데 가장 좋은 자료구조 이기 때문에 힙을 이용해 최소값을 계속해서 구한다. 

 

1. 우선 인접리스트를 보기 좋게 가공해서 쉽게 접근할 수 있도록 수정했다. 이때, 이 [(4,1)(1,2)] 값을 힙에 담을거라 힙 규칙에 따라 정렬이 필요한 원소를 앞에 배치하였다. 

Python에서 heap 사용하기, 힙큐(heapq)

graph[0] = [(4,1)(1,2)]
graph[1] = [(1,3)]
graph[2] = [(2,1)(5,3)]
graph[3] = [(3,4)]

 

 

이 데이터 이후에 필요한것은 아래와 같다. 

• 1. 가중치 값에 따른 정렬 → 힙으로 가중치에 따른 값 정렬 (힙에 담으면 최소값 순으로 자동정렬됨)
• 2. 현재 정점의 이웃 확인 → 다음 거리 계산 및 힙에 담을 값 확인 
• 3. 거리 확인 후 빈 값이면 dist insert 새 값이 더 작으면 update → 출발점까지 가중치 + 새로운 도착점까지 가중치
• 4. 최단 경로로 가야하니 heap에는 값이 insert/update 되었을때만 추가 

 

 

2. 위 내용을 바탕으로 직접 시뮬레이션 해본다 .... 이렇게 해보니까 이해가 더 잘 되었다..

 

 

 

어려웠던 점

1. float('inf')
   1. 양의 무한대를 의미한다. 최초 값은 이 값보다 무조건 작을 수밖에 없다.
2. 어떤식으로 흘러가는지 처음에 이해 자체가 어려웠는데, 이해하고 나니 이해가 되는? 느낌이다. 나중에 백지 상태에서 다시 풀어봐야할듯.