최단 경로 알고리즘
- 가장 짧은 경로를 찾는 알고리즘
- 길 찾기 문제
- 다양한 사례 ex
- 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우
- 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우
- 그래프를 이용 / 노드 : 지점, 간선 : 경로
다익스트라
- 가장 비용이 적은 노드를 선택하는 과정 반복 (= 그리디 알고리즘)
- 작동 과정
1. 출발 노드 설정
2. 최단 거리 테이블 초기화
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단거리 테이블 갱신
5. 3, 4 반복
1. 출발 노드 설정
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | INF | INF | INF | INF | INF |
- 1에서 시작
2. 최단 거리 테이블 초기화
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 5 | 1 | INF | INF |
- 1에서 갈 수 있는 각 노드까지의 거리 입력
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택
| 노드 번호 | 1(방문완료) | 2 | 3 | 4(선택) | 5 | 6 |
| 거리 | 0 | 2 | 5 | 1 | INF | INF |
- 노드 4 선택
- 노드 4에서는 노드 3, 5 방문 가능
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단거리 테이블 갱신
| 노드 번호 | 1(방문완료) | 2 | 3 | 4(선택) | 5 | 6 |
| 거리 | 0 | 2 | 5 -> 4 | 1 | INF -> 2 | INF |
- 노드 4 까지의 최단거리는 현재 1이므로 노드 4를 거쳐서 노드 3, 노드 5까지의 최단 거리는 4(1+3), 2(1+1)
- 현재 리스트에 있는 노드 3, 노드 5까지의 최단거리보다 짧으니까 둘다 갱신
- 위 작업을 선택할 노드가 없을 때 까지 진행
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택
| 노드 번호 | 1(방문완료) | 2(선택) | 3 | 4(방문완료) | 5 | 6 |
| 거리 | 0 | 2 | 4 | 1 | 2 | INF |
- 노드 2 선택 (노드 5도 거리가 2지만 일반적으로 같은 거리일 때는 번호가 작은거 고르자)
- 노드 2에서는 노드 3, 4 방문 가능
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단거리 테이블 갱신
| 노드 번호 | 1(방문완료) | 2(선택) | 3 | 4(방문완료) | 5 | 6 |
| 거리 | 0 | 2 | 4 | 1 | 2 | INF |
- 노드 2 까지의 최단거리는 현재 2이므로 노드 2를 거쳐서 노드 3, 노드 4까지의 최단 거리는 5(2+3), 4(2+2)
- 현재 리스트에 있는 둘다 리스트에 있는 최단거리보다 크니까 갱신 둘 다 안함
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택
| 노드 번호 | 1(방문완료) | 2(방문완료) | 3 | 4(방문완료) | 5(선택) | 6 |
| 거리 | 0 | 2 | 4 | 1 | 2 | INF |
- 노드 5 선택
- 노드 5에서는 노드 3, 6 방문 가능
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단거리 테이블 갱신
| 노드 번호 | 1(방문완료) | 2(방문완료) | 3 | 4(방문완료) | 5(선택) | 6 |
| 거리 | 0 | 2 | 4 -> 3 | 1 | 2 | INF -> 4 |
- 노드 5 까지의 최단거리는 현재 2이므로 노드 5를 거쳐서 노드 3, 노드 6까지의 최단 거리는 3(2+1), 4(2+2)
- 현재 리스트에 있는 노드 3, 노드 6까지의 최단거리보다 짧으니 둘 다 갱신
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택
| 노드 번호 | 1(방문완료) | 2(방문완료) | 3(선택) | 4(방문완료) | 5(방문완료) | 6 |
| 거리 | 0 | 2 | 3 | 1 | 2 | 4 |
- 노드 3 선택
- 노드 3에서는 노드 2, 6 방문 가능
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단거리 테이블 갱신
| 노드 번호 | 1(방문완료) | 2(방문완료) | 3(선택) | 4(방문완료) | 5(방문완료) | 6 |
| 거리 | 0 | 2 | 3 | 1 | 2 | 4 |
- 노드 3 까지의 최단거리는 현재 3이므로 노드 3를 거쳐서 노드 2, 노드 6까지의 최단 거리는 6(3+3), 8(3+5)
- 현재 리스트에 있는 노드 2, 노드 6까지의 최단거리보다 크니 둘 다 갱신 안함
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택
| 노드 번호 | 1(방문완료) | 2(방문완료) | 3(방문완료) | 4(방문완료) | 5(방문완료) | 6(선택) |
| 거리 | 0 | 2 | 3 | 1 | 2 | 4 |
- 노드 6 선택
- 노드 6에서는 방문 가능 노드 없음
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단거리 테이블 갱신
| 노드 번호 | 1(방문완료) | 2(방문완료) | 3(방문완료) | 4(방문완료) | 5(방문완료) | 6(선택) |
| 거리 | 0 | 2 | 3 | 1 | 2 | 4 |
최종
| 노드 번호 | 1(방문완료) | 2(방문완료) | 3(방문완료) | 4(방문완료) | 5(방문완료) | 6(방문완료) |
| 거리 | 0 | 2 | 3 | 1 | 2 | 4 |
- 한 단계당 하나의 최단 거리 확정
- 그 말은 마지막 단계에선 사실상 변동될 일이 없다는 뜻
간단한 다익스트라 알고리즘
- 작동원리 그대로 구현
- O(V^2) (V : 노드 개수)
- 전체 노드 개수가 5000개 이하면 문제없으나 10000개가 넘어가면 개선된 다익스트라 알고리즘
- 최단 거리가 가장 짧은 노드를 찾기 위해서 매번 최단 거리 테이블을 선형적으로 탐색
#다익스트라
MAP1 = [
[],
[(2,2),(3,5),(4,1)],
[(3,3),(4,2)],
[(2,3),(6,5)],
[(3,3),(5,1)],
[(3,1),(6,2)],
[]
]
INF = int(1e9)
def ds(MAP, node_num,start):
dis = [INF] * (node_num + 1)
dis_visited = [True] + [False] * node_num
dis[start] = 0
#선택할 수 있는 노드가 있는 동안
#dis 원소 중 가장 작은거 선택
#map[그 원소의 인덱스]
#튜플 두번째원소 거리 더하기 아까 가장 작은거
#그게 dis[첫번째원소] 보다 작으면 갱신
#노드 선택
while False in dis_visited:
MIN = [INF,INF] #값, 인덱스
for i in range(1,node_num+1):
if dis_visited[i] == False:
if MIN[0] > dis[i]:
MIN[0] = dis[i]
MIN[1] = i
for x,y in MAP[MIN[1]]:
if dis[x] > y + MIN[0]:
dis[x] = y + MIN[0]
dis_visited[MIN[1]] = True
#print("debug",dis_visited)
#print(dis)
return dis
print(ds(MAP1,6,1))
개선된 다익스트라 알고리즘
- WORST CASE 에도 O(ElogV) (E : 간선 개수, V : 노드 개수)
- 최단 거리가 가장 짧은 노드를 찾는 과정을 개선
직접 짰는데 결과는 맞지만 큐가 이상하게 삽입이 더 많이 되는 문제가 있는 버전
#개선된 다익스트라
import heapq
n, m = map(int,input().split()) #노드, 간선
start = int(input())
graph = [[] for x in range(n+1)]
for _ in range(m):
a, b, c = map(int,input().split())
graph[a].append([b,c])
def ds(GRAPH, START):
INF = int(1e9)
q = []
NODE_NUM = len(GRAPH)-1
dist = [INF] * (NODE_NUM+1)
q = [(0, START)]
#큐에 있을 동안
#큐에서 꺼낸게 현재 거리정보와 비교했을 때 더 짧으면
#갱신
#현재거리 + 다음거리가 다음 노드의 최단거리보다 짧으면
#현재 거리 + 다음 노드 거리 들을 큐에 삽입
#아니면
#다음 큐 꺼냄
while q:
now_dis, now = heapq.heappop(q)
print('poped', q)
if dist[now] > now_dis:
dist[now] = now_dis
for next_, next_dis in GRAPH[now]:
if next_dis + dist[now] < dist[next_]:
heapq.heappush(q,(next_dis + dist[now],next_))
print('pushed', q)
else:
continue
return dist
print(ds(graph,1))
책 정답 버전
import heapq
import sys
input = sys.stdin.readline
INF =int(1e9)
n, m = map(int,input().split())
start = int(input())
graph = [[] for i in range(n+1)]
distance = [INF] * (n+1)
for _ in range(m):
a ,b, c= map(int,input().split())
graph[a].append((b,c))
def ds(start):
q = []
heapq.heappush(q, (0, start))
distance[start]=0
while q:
dist,now=heapq.heappop(q)
print('pop',q)
if distance[now]<dist:
continue
for i in graph[now]:
cost=dist+i[1]
if cost<distance[i[0]]:
distance[i[0]]=cost
heapq.heappush(q,(cost,i[0]))
print('push',q)
print(ds(start))직접 짠거 수정 버전
#개선된 다익스트라
import heapq
n, m = map(int,input().split()) #노드, 간선
start = int(input())
graph = [[] for x in range(n+1)]
for _ in range(m):
a, b, c = map(int,input().split())
graph[a].append([b,c])
def ds(GRAPH, START):
INF = int(1e9)
q = []
NODE_NUM = len(GRAPH)-1
dist = [INF] * (NODE_NUM+1)
q = [(0, START)]
dist[START] = 0
#큐에 있을 동안
#큐에서 꺼낸게 현재 거리정보와 비교했을 때 더 짧으면
#현재거리 + 다음거리가 다음 노드의 최단거리보다 '같거나' 짧으면
#현재 거리 + 다음 노드 거리 들을 큐에 삽입
#갱신
#아니면
#다음 큐 꺼냄
while q:
now_dis, now = heapq.heappop(q)
print('poped', q)
if dist[now] >= now_dis:
for next_, next_dis in GRAPH[now]:
if next_dis + dist[now] < dist[next_]:
heapq.heappush(q,(next_dis + dist[now],next_))
dist[next_] = next_dis + dist[now]
print('pushed', q)
else:
continue
return dist
print(ds(graph,1))
플로이드 워셜
- 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우
- N 번의 단계마다 O(N^2) 번의 연산 -> O(N^3)
- 다익스트라 최단거리 정보 == 1차원 리스트, 플로이드 워셜 최단거리 리스트 == 2차원 리스트
- 다이나믹 프로그래밍 - 노드의 개수 만큼의 단계를 반복하며 점화식에 맞게 2차원 리스트를 갱신하기 때문
- 점화식 : D<a,b> = min(D<a,b>, D<a,k> + D<k,b>)
n, m = map(int,input().split())
# 1 2 3 4
#1
#2
#3
#4
INF = int(1e9)
graph = [[INF]*(n+1) for x in range(n+1)]
for i in range(1,n+1):
graph[i][i] = 0
for i in range(m):
a, b, c = map(int, input().split())
graph[a][b] = c
#1~n 번째 노드를 거쳐서 목적지에 가는 방법
#j마다
#k마다
#graph[j][k]에서 j나 k중 하나가 거치는 노드랑 같으면
#컨티뉴
#현재 위치와 노드를 거쳤을 때 둘중 거리가 짧은 것 선택, 갱신
for i in range(1,n+1):
for j in range(1,n+1):
for k in range(1,n+1):
if j == i or k == i:
continue
graph[j][k] = min(graph[j][k], graph[j][i] + graph[i][k])
print(graph)
EZ
문제 1. 미래 도시 (난이도 2, 풀이 시간 17분/40분, 정답)
#미래도시 2:54 3:11
#도시 간 간격 일정 1
#1 -> K -> X
#1->K의 최소이동값 + K->X의 최소이동값
N, M = map(int,input().split()) #회사개수 경로개수
INF = int(1e9)
graph = [[INF]*(N+1) for _ in range(N+1)]
for i in range(1,N+1):
graph[i][i] = 0
for _ in range(M):
a,b = map(int, input().split())
graph[a][b] = 1
graph[b][a] = 1
X, K = map(int,input().split())
for i in range(1,N+1):
for j in range(1,N+1):
for k in range(1,N+1):
if j == i or k == i:
continue
graph[j][k] = min(graph[j][k], graph[j][i] + graph[i][k])
res = graph[1][K]+graph[K][X]
if res >= INF:
print(-1)
else:
print(res)
- 플로이드 워셜로 전체 노드에서 전체 노드까지 최단거리 구해놓고 1->K + K->X 하면 간단히 풀리는 문제
- N의 범위가 100 이하로 매우 한정적이어서 O(N^3)인 플로이드 워셜 알고리즘을 써도 빨리 풀 수 있었다.
문제 2. 전보 (난이도 3, 58분/60분, 틀림)
내 오답
import heapq
#전보 3:22 4:20
#X->Y일방향 통로, 보낼땐 일정시간소요
#한 도시에서 출발하여 메세지를 최대한 많이 퍼져나가게, 도시들이 모두 메세지를 받는데 걸리는 시간(제일 경로가 긴 곳 도달 시간)
#최대한 긴 한붓그리기
#정해진 시작지점 하나부터 최장경로 = 다익스트라, 도시간 거리가 1이라고 가정시에 -1로 최단경로
#
N, M, C = map(int,input().split()) #도시개수, 통로개수, 스타트 도시
INF = int(1e9)
graph = [[] for _ in range(N+1)]
for _ in range(M):
a,b,c = map(int, input().split())
graph[a].append((b,c)) #목적지, 거리
def ds(GRAPH, START):
q = []
dist = [[INF,0] for _ in range(N+1)]
heapq.heappush(q,(0,START))
while q:
now_dist, now = heapq.heappop(q)
if dist[now][0] >= now_dist:
for next_, next_dist in GRAPH[now]:
if -1 + now_dist < dist[next_][0]:
dist[next_][0] = -1 + now_dist
dist[next_][1] = next_dist + dist[now][1]
heapq.heappush(q,(-1,next_))
else:
continue
return dist
city = 0
max_time = 0
for i in ds(graph,C):
if i[0] < 0 and i[0] != INF:
city += 1
if max_time < i[1]:
max_time = i[1]
print(city,max_time)
import heapq
#전보 3:22
#X->Y일방향 통로, 보낼땐 일정시간소요
#한 도시에서 출발하여 메세지를 최대한 많이 퍼져나가게, 도시들이 모두 메세지를 받는데 걸리는 시간(제일 경로가 긴 곳 도달 시간)
N, M, C = map(int,input().split()) #도시개수, 통로개수, 스타트 도시
INF = int(1e9)
graph = [[] for _ in range(N+1)]
for _ in range(M):
a,b,c = map(int, input().split())
graph[a].append((b,c)) #목적지, 거리
def ds(GRAPH, START):
q = []
dist = [INF]*(N+1)
dist[START] = 0
heapq.heappush(q,(0,START))
while q:
now_dist, now = heapq.heappop(q)
if dist[now] >= now_dist:
for next_, next_dist in GRAPH[now]:
if next_dist + now_dist < dist[next_]:
dist[next_] = next_dist + now_dist
heapq.heappush(q,(next_dist,next_))
else:
continue
return dist
dist = ds(graph,1)
#방문 가능한 노드의 개수 = 메세지를 받는 총 도시의 개수 = 다익스트라 거리정보 개수 - 출발지,INF
res = 0
max_dist = 0
for i in dist:
if i != INF and i != 0:
res += 1
max_dist = max(max_dist, i)
print(res, max_dist)
- 방문 가능한 노드 개수 = 메세지 전송 가능한 총 도시 개수
- 다익스트라 거리 정보에 있는 값 중 INF 제외 제일 큰게 총 시간