20. 최단 경로 문제 - 다익스트라 알고리즘

 그래프의 종류와 특성에 따라 각각 최적화된 다양한 최단 경로 알고리즘이 존재한다. 이 중에서 가장 유명한 것은 다익스트라 알고리즘이다. 

 

 다익스트라 알고리즘은 항상 노드 주변의 최단 경로만을 택하는 대표적인 그리디(Greedy)알고리즘 중 하나로, 단순할 뿐만 아니라 실행 속도 또한 빠르다. 다익스트라 알고리즘은 노드 주변을 탐색할 때 BFS를 이용하는 대표적인 알고리즘이기도 하다.

 

 다익스트라 알고리즘은 임의의 정점을 출발 집합에 더할 때, 그 정점까지의 최단거리는 계산이 끝났다는 확신을 갖고 더한다. 만일 이후에 더 짧은 경로가 존재한다면 다익스트라 알고리즘의 논리적 기반이 무너진다.

https://leetcode.com/problems/network-delay-time/

Network Delay Time - LeetCode

 k부터 출발해 모든 노드가 신호를 받을 수 있는 시간을 계산하라. 불가능할 경우 -1을 리턴한다. 입력값(u,v,w)는 각각 출발지, 도착지, 소요 시간으로 구성되며, 전체 노드의 개수는 N으로 입력받는다.

 

 이 문제에서는 다음과 같은 2가지 사항을 판별해야 한다.

 1. 모든 노드가 신호를 받는 데 걸리는 시간 - 가장 오래 걸리는 노드까지의 시간

 2. 모든 노드에 도달할 수 있는지 여부 - 만약 노드가 8개인데 다익스트라 알고리즘 계산은 7개밖에 할 수 없다면 -1을 리턴

 

 다익스트라 알고리즘을 좀 더 효율적으로 구현하기 위해 다익스트라가 1950년대에 처음 구현한 방식과 달리, 우선순위 큐를 적용하는 방식을 사용한다. 파이썬에서 우선순위 큐를 최소 힙으로 구현한 모듈일 heapq를 사용하는 형태로 구현해본다. 

 

 

1. 먼저 그래프를 구성한다. 그래프를 인접 리스트로 표현하는 딕셔너리부터 만들어준다.

2. 우선순위 큐를 위한 큐 변수를 정의한다.

 큐 변수 Q는 (소요시간, 정점) 구조로 구성한다. 즉 시작점에서 정점까지의 소요 시간을 담아둘 것이다.

 

 dist에 node의 포함 여부부터 체크한다. dist에 아무 값도 세팅하지 않았기 때문에 처음에는 이 값이 비어 있을 것이고, 이 경우에만 힙에 push 하는 형태로 조금 다르게 구현할 것이다. 이렇게 하면 큐의 우선순위를 업데이트 할 필요 없이 존재 유무로만 진행할 수 있으며, dist에는 항상 최솟값이 세팅될 것이다.

 

 마지막으로 모든 노드에 도달할 수 있는지 여부를 다음과 같이 판별한다.

 여기서는 dist 딕셔너리의 키 개수가 N과 동일한지 체크한다. 전체 노드 개수만큼이 모두 dist에 있다면 모든 노드의 최단 경로를 구했다는 의미고, 이는 모두 시작점에서 도달이 가능하다는 의미기도 하다.

import collections
import heapq

class Solution:
    def networkDelayTime(self, times, n, k):
        graph=collections.defaultdict(list)
        for u,v,w in times:
            graph[u].append((v,w))
        
        Q=[(0,k)]  # 우선순위큐
        dist=collections.defaultdict(int)


        while Q:
            time,node=heapq.heappop(Q)
            if node not in dist:
                dist[node]=time
                for v,w in graph[node]:
                    alt=time+w
                    heapq.heappush(Q,(alt,v))

        if len(dist) == n:
            return max(dist.values())

        return -1