ALGORITHM| 최단경로, 다익스트라로 문제 풀이
최단 경로 문제 풀이 중에서 다익스트라
『파이썬 알고리즘 인터뷰』
- 최단 경로 문제
- 다익스트라 알고리즘(Dijkstra)
- Leetcode 743, Network Delay Time
- Leetcode 787, Cheapest Flights Within K Stops
최단 경로 문제
각 간선의 가중치 합이 최소가 되는 두 정점(노드) 사이의 경로를 찾는 문제
정점(Vertex): 교차로
간선(Edge): 길
가중치(Weight): 거리, 시간
그래프의 종류와 특성에 따라 각각 최적화된 다양한 최단 알고리즘이 존재 ex) 다익스트라 알고리즘
다익스트라 알고리즘(Dijkstra)
항상 노드 주변의 최단 경로만을 택하는 대표적인 그리디(Greedy) 알고리즘 중 하나, 단순하고 실행 속도가 빠름. BFS를 이용하는 대표적인 알고리즘이다.
- DFS(깊이 우선 탐색): 한사람이 미로를 찾아 헤매는 과정
- BFS(너비 우선 탐색): 여러명의 사람이 각기 서로 다른 갈림길로 흩어져서 길을 찾는 것과 비슷
- 이때 각자 실뭉치를 가지고 풀어놓았다가 되감으면서 새로운 길을 탐색, 길을 따라가다 갈림길이 나오면 사람들을 나눠 다시 각자 새로운 길을 탐색하고, 다시 갈림길을 만나 새로운 길이 하나로 모이면 나뉘어 탐색하던 사람들이 다시 모여서 함께 탐색한다.
- 다익스트라 알고리즘: 이때 먼저 도착한 사람의 실뭉치를 사용한다. 하지만 가중치가 음수인 경우 처리가 불가하다.
임의의 정점을 출발 집합에 더할 때, 그 정점까지의 최단거리는 계산이 끝났다고 확신을 갖고 더한다. 만일 이후에 더 짧은 경로가 존재한다면 다익스트라 알고리즘의 논리적 기반이 무너진다.
이때는 모든 값을 더해서 양수로 변환하는 방법이 있는데 어려우면 벨만-포드 알고리즘 같은 음수 가중치를 계산하는 다른 알고리즘을 사용해야한다. 같은 이유로 최장 거리를 구하는데에는 다익스트라 알고리즘을 사용할 수 없다.
다익스트라 시간복잡도
최초 구현: O(V^2)
BFS시 가장 가까운 순서를 찾을 때 우선순위 큐 적용: O((V+E) log V)
모든 정점이 출발지에서 도달이 가능하다면: O(E log V)
Leetcode 743, Network Delay Time
https://leetcode.com/problems/network-delay-time/
K부터 출발해 모든 노드가 신호를 받을 수 있는 시간을 계산, 불가능할 경우 -1을 리턴
다익스트라 알고리즘 구현
2가지를 판별해야함
- 모든 노드가 신호를 받는 데 걸리는 시간
- 가장 오래 걸리는 노드까지의 최단 시간을 말함 → 다익스트라 알고리즘으로 추출
- 모든 노드에 도달할 수 있는지 여부
- 모든 다익스트라 알고리즘 계산 값이 존재하는지 유무로 판별할 수 있음, 만약 노드가 8개인데 다익스트라 알고리즘 계산은 7개 밖에 할 수 없다면 나머지 한 노드에는 도달할 수 없어서 -1을 리턴
다익스트라 알고리즘 수도코드
function Dijkstra(Graph, source):
dist[source] <- 0
create vertex priority queue Q
for each vertex v in Graph: # 이웃을 살펴보는 부분
if v != source
dist[v] <- INFINITY
prev[v] <- UNDEFINED # prev[v]는 이전 노드의 값
Q.add_with_priority(v, dist[v]) # 그래프에서 각 정점과 거리를 우선순위 큐에 삽입
while Q is not empty:
u <- Q.extract_min() # 우선순위 큐에서 최소 값을 추출
for each neighbor v of u:
alt <-dist[u] + length(u, v)
if alt < dist[v]
dist[v] <- alt
prev[v] <- u
Q.decrease_priority(v, alt)
return dist, prev
파이썬 구현
처음 구현된 방식과 달리 우선순위 큐를 최소 힙으로 구성한 모듈인 heapq를 사용한 형태로 구현
dist는 초깃값을 무한대로 설정한 수도코드와 달리 구현 → heapq 모듈은 우선순위 업데이트를 지원하지 않음 → 우선순위를 업데이트하려면 먼저 해당되는 키를 찾아야 하므로 O(n)의 시간복잡도 필요해서 → decrease_priority()의 연산이 필요없도록 변경
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))
수도 코드에서 for each 구문으로 이웃 노드를 순회했지만 먼저 dist에서 node의 포함 여부부터 체크함 → dist에 아무 값도 세팅하지 않았기에
이렇게 하면 큐의 우선순위를 업데이트할 필요 없이 존재 유무로만 진행할 수 있으며 dist에는 항상 최솟값이 세팅될 수 있음
def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:
graph = collections.defaultdict(list)
# 그래프 인접 리스트 구성
for u, v, w in times:
graph[u].append((v, w))
# 큐 변수: [(소요 시간, 정점)]
# ‘정점’까지의 소요 시간을 담을 것, 초기값은 시작점 K부터이므로 소요 시간은 0 → (0, K)
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: # 전체 노드 개수만큼 모두 dist에 있다면 구했음
return max(dist.values())
return -1
수도 코드의 prev[v]는 이전 노드의 값인데, 이 문제에는 이전 노드가 무엇인지 여부는 필요없어서 제외됨
Leetcode 787, Cheapest Flights Within K Stops
https://leetcode.com/problems/cheapest-flights-within-k-stops/description/
시작점에서 도착점까지의 가장 저렴한 가격을 계산하되 K개의 경유지 이내에 도착하는 가격을 리턴, 경로가 존재하지 않을 경우 -1
다익스트라
- 추가된점: K개의 경유지 이내에 도착해야함
class Solution:
def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
graph = collections.defaultdict(list)
# 그래프 인접 리스트 구성
for u, v, w in flights:
graph[u].append((v, w))
# 큐 변수: [(가격, 정점, 남은 가능 경유지 수)]
Q = [(0, src, k)]
# 우선순위 큐 최솟값 기준으로 도착지까지 최소 비용 판별
while Q:
price, node, k = heapq.heappop(Q)
if node == dst:
return price
if k >= 0:
for v, w in graph[node]:
alt = price + w
heapq.heappush(Q, (alt, v, k-1))
return -1
