*최단경로 알고리즘: 특정 지점까지 가장 빠르게 도달하는 방법을 찾는 알고리즘
*최단경로 알고리즘의 종류
1) 다익스트라 알고리즘
2) 플로이드 워셜 알고리즘
3) 벨만 포드 알고리즘
코딩테스트에 자주 나오며 면접에서도 꼭 알아둬야 하는 개념이다.
*최단경로 문제 형태
Q. 한 지점에서 다른 특정 지점까지의 최단 경로(거리, 시간, 비용, etc)를 구해야 하는 경우
Q. 모든 지점에서 다른 모든 지점까지 최단 경로(거리, 시간, 비용, etc)를 모두 구해야 하는 경우
각 주제에 대해 다음 순으로 포스팅하려 한다.
1) 다익스트라 알고리즘 -> 2) 플로이드 워셜 알고리즘 -> 3) 벨만 포드 알고리즘
*다익스트라 알고리즘
1. 정의
그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단경로를 구해주는 알고리즘
2. 특징
1) '음의 간선'이 없을 때만 정상적으로 동작 (음의 간선=0보다 작은 값을 가지는 간선)
2) GPS 소프트웨어의 기본 알고리즘으로 채택됨
3) 매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복하기 때문에, 그리디 알고리즘으로 분류됨
3. 알고리즘 원리
1) 출발 노드를 설정한다
2) 최단 거리 테이블을 초기화한다
3) 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다
4) 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다
5) 위 과정에서 3)번과 4)번을 반복한다
위 동작 과정을 그림으로 잘 설명된 사이트를 보려면 아래 사진 속 링크를 보길 바란다.
4. 구현 방식
1) priority queue 사용하지 않은 코드 (not recommended)
(수도 코드)
1 function Dijkstra(Graph, source):
2
3 create vertex set Q
4
5 for each vertex v in Graph: // 초기화
6 dist[v] ← INFINITY // 소스에서 v까지의 아직 모르는 길이
7 prev[v] ← UNDEFINED // 소스에서 최적 경로의 이전 꼭짓점
8 add v to Q // 모든 노드는 초기에 Q에 속해있다 (미방문 집합)
9
10 dist[source] ← 0 // 소스에서 소스까지의 길이
11
12 while Q is not empty:
13 u ← vertex in Q with min dist[u] // 최소 거리를 갖는 꼭짓점
14 // 을 가장 먼저 선택한다
15 remove u from Q
16
17 for each neighbor v of u: // v는 여전히 Q에 있다.
18 alt ← dist[u] + length(u, v)
19 if alt < dist[v]: // v 까지의 더 짧은 경로를 찾았을 때
20 dist[v] ← alt
21 prev[v] ← u
22
23 return dist[], prev[]
(파이썬 코드)
'''
# dijkstra algorithm without priorityQueue
# time complexity : O(V^2)
# space complexity : O(V+E)
'''
import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정
# edges -> graph 만들기: O(E)
def edges2graph(edges, n):
graph = [[] for i in range(n+1)] # sc: O(V)
for start, dest, cost in edges: # tc: O(E)
graph[start].append((dest, cost))
return graph
# 방문하지 않은 노드 중에서, 가장 최단 거리가 짧은 노드의 번호를 반환 : O(V)
def get_smallest_node(distance, visited):
min_value = INF
index = 0 # 가장 최단 거리가 짧은 노드(인덱스)
for i in range(1, n+1):
if distance[i] < min_value and not visited[i]:
min_value = distance[i]
index = i
return index
# 다익스트라 알고리즘 : O(V^2)
def dijkstra(graph, pos, n):
# 방문한 적이 있는지 체크하는 목적의 리스트 # sc: O(V)
visited = [False] * (n + 1)
# 최단 거리 테이블을 모두 무한으로 초기화 # sc: O(V)
distance = [INF] * (n + 1)
# 시작 노드에 대해서 초기화
distance[pos] = 0
visited[pos] = True
for j in graph[pos]:
distance[j[0]] = j[1]
# 시작 노드를 제외한 전체 n - 1 개의 노드에 대해 반복 : O(V^2)
for i in range(n-1): # tc: O(V)
# 현재 최단 거리가 가장 짧은 노드를 꺼내서, 방문 처리
now = get_smallest_node(distance, visited) # tc: O(V)
visited[now] = True
# 현재 노드와 연결된 다른 노드 확인 # O(V) (node-node 간 중복된 edge가 있으면 O(E))
for j in graph[now]:
cost = distance[now] + j[1]
# 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
if cost < distance[j[0]]:
distance[j[0]] = cost
return distance
def solve(n, m, pos, edges):
# edges -> graph
graph = edges2graph(edges, n)
# dijkstra
distance = dijkstra(graph, pos, n) # 그래프, 시작위치,노드 개수
# 모든 노드로 가기 위한 최단 거리 반환
return distance
if __name__ == "__main__":
# 노드의 개수, 간선의 개수를 입력받기
n, m = map(int, input().split())
# 시작 노드 번호를 입력받기
pos = int(input())
# 간선 정보 입력받기
edges = [list(map(int, input().split())) for _ in range(m)] # sc: O(E)
distance = solve(n, m, pos, edges)
# 모든 노드로 가기 위한 최단 거리 출력
for i in range(1, n+1):
if distance[i] == INF:
print("INFINITY")
else:
print(distance[i])
2) priority queue 사용한 코드 (recommended)
(수도 코드)
1 function Dijkstra(Graph, source):
2 dist[source] ← 0 // 초기화
3
4 create vertex set Q
5
6 for each vertex v in Graph:
7 if v ≠ source
8 dist[v] ← INFINITY // 소스에서 v까지의 아직 모르는 길이
9 prev[v] ← UNDEFINED // v의 이전 노드
10
11 Q.add_with_priority(v, dist[v])
12
13
14 while Q is not empty: // 메인 루프
15 u ← Q.extract_min() // 최고의 꼭짓점을 제거하고 반환한다
16 for each neighbor v of u: // Q에 여전히 남아 있는 v에 대해서만
17 alt ← dist[u] + length(u, v)
18 if alt < dist[v]
19 dist[v] ← alt
20 prev[v] ← u
21 Q.decrease_priority(v, alt)
22
23 return dist, prev
(파이썬 코드)
'''
# dijkstra algorithm using priorityQueue
# time complexity : O(ElogV)
# space complexity : O(V+E)
'''
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정
# edges -> graph 만들기: O(E)
def edges2graph(edges, n):
graph = [[] for i in range(n+1)] # sc: O(V)
for start, dest, cost in edges: # tc: O(E)
graph[start].append((dest, cost))
return graph
# 다익스트라 알고리즘 : O(ElogV)
def dijkstra(graph, pos, n):
q = []
distance = [INF] * (n + 1) # 최단 거리 테이블을 모두 무한으로 초기화 sc: O(V)
# 시작노드로 가기 위한 최단 경로는 0으로 설정해, 큐에 삽입
heapq.heappush(q, (0, pos))
distance[pos] = 0
# tc: O(ElogV), sc: O(E)
while q: # 큐가 비어있지 않다면
# 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
dist, now = heapq.heappop(q)
# 현재 노드가 이미 처리된 적이 있는 노드라면 무시
if distance[now] < dist:
continue
# 현재 노드와 연결된 다른 인접한 노드들 확인
for i in graph[now]:
cost = distance[now] + i[1]
# 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
if cost < distance[i[0]]:
distance[i[0]] = cost
heapq.heappush(q, (cost, i[0]))
return distance
def solve(n, m, pos, edges):
# edges -> graph
graph = edges2graph(edges, n)
# dijkstra
distance = dijkstra(graph, pos, n) # 그래프, 시작위치,노드 개수
# 모든 노드로 가기 위한 최단 거리 반환
return distance
if __name__ == "__main__":
# 노드의 개수, 간선의 개수를 입력받기
n, m = map(int, input().split())
# 시작 노드 번호를 입력받기
pos = int(input())
# 간선 정보 입력받기
edges = [list(map(int, input().split())) for _ in range(m)] # sc: O(E)
distance = solve(n, m, pos, edges)
# 모든 노드로 가기 위한 최단 거리 출력
for i in range(1, n+1):
if distance[i] == INF:
print("INFINITY")
else:
print(distance[i])
5. 시간복잡도/공간복잡도
| time complexity | space complexity | |
| priority queue 사용x | O(V^2) | O(V+E) |
| priority queue 사용o | O(ElogV) | O(V+E) |
관련 문제
위 문제 코드와 같다.
관련 질문
Q. 다익스트라 알고리즘은 무엇인가?
A.
다익스트라 알고리즘은 최단 경로 알고리즘 중 하나로,
그래프에서 여러 개의 노드가 있을 때,
특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단경로를 구해주는 알고리즘입니다.
매번 가장 비용이 적은 노드를 선택해서 해당 노드와 연결된 다른 노드를 방문해 거리를 update 해주는 방식이며,
priority queue를 이용해 구현할 수 있습니다.
priority queue를 이용해 구현하면 시간 복잡도는 O(ElogV), 공간 복잡도는 O(V+E)입니다.
Q. 다익스트라 알고리즘의 time complexity, space complexity
A.
priority queue를 이용하지 않고 매번 가장 짧은 거리를 가지는 노드를 찾아서 구현하는 방식을 사용하면
time complexity는 O(V^2), 공간복잡도는 O(V+E)입니다.
하지만 (현재 해당 노드까지의 거리, 해당 노드)를 priority queue에 넣어주는 방식으로 구현하면,
time complexity는 O(ElogV), 공간복잡도는 O(V+E)입니다.
Q. 다익스트라 알고리즘 구현 & 각 부분별 time complexity, space complexity 설명
A.
# 다익스트라 알고리즘 : O(ElogV)
def dijkstra(graph, pos, n):
q = []
distance = [INF] * (n + 1) # 최단 거리 테이블을 모두 무한으로 초기화 sc: O(V)
# 시작노드로 가기 위한 최단 경로는 0으로 설정해, 큐에 삽입
heapq.heappush(q, (0, pos))
distance[pos] = 0
# tc: O(ElogV), sc: O(E)
while q: # 큐가 비어있지 않다면
# 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
dist, now = heapq.heappop(q)
# 현재 노드가 이미 처리된 적이 있는 노드라면 무시
if distance[now] < dist:
continue
# 현재 노드와 연결된 다른 인접한 노드들 확인
for i in graph[now]:
cost = distance[now] + i[1]
# 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
if cost < distance[i[0]]:
distance[i[0]] = cost
heapq.heappush(q, (cost, i[0]))
return distance
Q. 최단 경로를 출력하려면?
A.
00000
Q. 최단 거리를 만드는 모든 최단 경로를 출력하려면?
A.
00000
-참고문헌
'Computer Science > Datastructure & Algorithm' 카테고리의 다른 글
| 이분탐색(Binary Search) vs 투포인터(Two Pointer) 알고리즘 (0) | 2021.04.18 |
|---|---|
| adjacency matrix로 구현된 graph를 DFS할 때 time complexity (0) | 2021.02.14 |
| Q. 문자열을 뒤집는 모든 방법 (0) | 2021.02.01 |
