-
[알고리즘] 최단경로 정리알고리즘 2022. 9. 26. 15:33728x90
최단경로 - 가장짧은 경로 찾기
- 다이나믹도 가능하다
- 그래프에서 각 지점을 노드와 간선으로 표시
- 문제상황
- 한지점에서 다른 지점까지 경로
- 한지점에서 다른 모든 지점까지의 경로
- 모든 지점에서 다른 모든 지점까지의 경로
input() -> sys.std.realine()으로 치환
다익스트라 알고리즘 ( 시간복잡도 O(V**2) V는 노드 수 )
- 특정 노드에서 다른 모든 노드로의 경로 **
- 음의간선이 없다!
- 그리디로 분류, 매 상황 가장 적은 비용 노드 찾기
- 노드 개수 = V일때, 선형탐색은 V ≤ 5000, V > 5000이면 ‘우선순위 큐’ 사용
- 동작순서 **
- 출발노드 선택
- 최단 거리 테이블 초기화 ( 1차원 리스트를 무한으로 초기화 하는 것이다 )
- graph = [[] for i in range(n+1)] # 모든 리스트는 ( 노드 개수 + 1 ) 로 해주기 # 무한으로 초기화 ( 정수형 ) int(1e9)
- 방문 하지 않은 노드 중, 가장 짧은 노드 선택 → 그리디도 분류
- 1차원 리스트 모든 원소 검색 → 순차 탐색
- 해당 노드를 거쳐, 다른 노드로 가는 비용을 계산해 최단거리 테이블 갱신
# 매 단계마다 1차원 테이블의 모든 원소를 확인(순차 탐색) import sys imput = sys.stdin.readline() INF = int(1e9) n,m = map(int,input().split()) start = int(input()) graph = [[] for in range(n+1)] # 각 노드에 연결된 노드 정보 담기 visited = [False] * (n+1) # 방문 체크 목적의 리스트 만들기 distance = [INF]*(n+1) # 최단거리 테이블 모두 초기화 for _ in range(m): # 모든 간선 정보 받기 a,b,c = map(int,input().split()) graph[a].append((b,c)) def get_smallest_node(): #방문하지 않은 노드중 가장 짧은 거리 노드 반환 min_value = INF index = 0 # 최단거리가 짧은 노드 (IDX) for i in range(1,n+1): if distance[i] < min_value and not visited[i]: min_value = distance[i] index = i return index def dijkstra(start): distance[start] = 0 # 시작노드 초기화 visited[start] = True for j in graph[start]: distance[j[0]] =j[1] for i in range(n-1): #시작 노드 제외 N-1개 노드 반복 now = get_smallest_node() visited[now] = True for j in graph[now]: #현재 노드와 연결된 노드 확인 cost = distance[now] + j[1] if cost < distance[j[0]]: #현재 노드를 거쳐 다른 노드로 이동하는 거리가 짧은경우 distance[j[0]] = cost dijkstra(start) for i in range(1,n+1): #모든 경로로 가기 위한 최단거리 if distance[1] == INF: # 도달 못함 print("infinitiy") else: #도달함, 거리출력 print(distance[i])
개선된 다익스트라 → 우선순위 큐 - 우선순위가 높은 데이터 먼저 삭제
- heapq 사용 → 내부적으로 최소힙, 최대힙을 사용
- 최소힙을 default로 생각하고 접근해야함 ( 값이 낮은 데이터 먼저 삭제 )
- 최소힙은 우선순위에 음수부호 (-)를 먼저 붙였다가 우선순위에서 꺼낸 다음에 다시 음수부호를 붙여서 원래대로 바꾼다
- 튜플을 이용해 우선순위 큐에 데이터를 넣는다. < ex) (0,1) 0은 거리, 1은 노드번호 >
- heap 사용
- 중복 간선x = O(ElogV) - E는 최대 간선개수, V는 노드 개수
- 중복 간선o = O(ElogE) - E는 최대 간선개수
- 최소힙(min heap) - 최소합 값이 낮은 데이터 부터 추출 = 오름차순 (heapq.heappush(h,v))
- 최대힙(max heap) - 최대합이 높은 데이터 부터 추출 = 내림차순 (heapq.heappush(h,-v))
- 트리에서 모든 노드 개수 = N 이면, 간선개수는 n-1
- 힙은 이진탐색트리를 따름
- 트리순회
- 전위 : 루트 - 왼 - 오른쪽 노드
- 중위: 왼 - 루트 - 오른쪽 노드
- 후위 : 왼 - 오른쪽- 루트 노드
- 트리순회
#위 다익스트라 + 우선순위 큐 import sys import heapq imput = sys.stdin.readline() INF = int(1e9) n,m = map(int,input().split()) start = int(input()) graph = [[] for 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 dijkstra(start): q = [] heapq.heappush(q,(0,start)) # 시작노드로 가기위한 최단거리는 0으로 설정, q에 삽입 distance[start] = 0 # 시작노드 초기화 while q: dist,now = heapq.heappop(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.heqppush(q, ( cost, i[0] )) dijkstra(start) for i in range(1,n+1): #모든 경로로 가기 위한 최단거리 if distance[1] == INF: # 도달 못함 print("infinitiy") else: #도달함, 거리출력 print(distance[i])
플로이드 워셜 O(N^3)
- 노드가 500개 미만일때만 가능
- 테이블를 무한으로 초기화 ( 2차원 리스트 )
- graph = [[INF] * (n+1) for _ in range(n+1) ]
- 다익스트라 처럼 매 단계별 거쳐가는 노드를 기준으로 수행하지만, 매 단계마다 방문하지 않은 노드 중 최단거리를 갖는 노드를 찾지 않는다
- 정화식 : 특정한 노드 k를 거쳐 가는 경우를 확인 ( a→b or a→k→b 뭐가 더 짧은지 )
- D(ab) = min (D(ab), D(ak) + D(kb))
INF = int(1e9) n , m = int(input().split()) # 노드, 간선 수 graph = [[INF]*(n+1) for _ in range(n+1) ] #자기 자신으로 이동하는 비용은 0 for a in range(1,n+1): for b in range(1,n+1): if a==b: graph[a][b] = 0 # 간선에 대한 정보를 입력 받아 , 그 값으로 초기화 for _ in range(m): a,b,c = map(int,input().split()) graph[a][b] = c # a->b 비용은 c # 점화식 for k in range(1,n+1): for a in range(1,n+1): for b in range(1, n+1): graph[a][b] = min(graph[a][b], graph[a][k]+graph[k][b]) #결과 for a in range(1,n+1); for b in range(1,n+1): #도달 못한 경우 if graph[a][b] == INF: print("도달못함") else: print(graph[a][b**])**
문제1) 전보
수행과정
- N개 도시 (x → y)로 이동
- 방향성이 있는 간선 : M ( n ≤ 30.000, m ≤ 200.000 )
- 한 도시에서 보낸 메세지를 받는 도시의 총 개수, 총 걸리는 시간
idea
- 한도시 → 다른도시 : “ 최단거리 “
- 노드 개수가 많아서 heap을 이용한 다익스트라 쓰기 ( 플로이드 아님 )
import sys import heap imput = sys.stdin.readline() INF = int(1e9) n,m = map(int,input().split()) start = int(input()) distance = [INF]*(n+1) # 최단거리 테이블 모두 초기화 for _ in range(m): # 모든 간선 정보 받기 a,b,c = map(int,input().split()) graph[a].append((b,c)) def dijkstra(start): q = [] heapq.heappush(q,(0,start)) # 시작노드로 가기위한 최단거리는 0으로 설정, q에 삽입 distance[start] = 0 # 시작노드 초기화 while q: dist,now = heapq.heappop(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.heqppush(q, ( cost, i[0] )) dijkstra(start) count = 0 # 도달할 수 있는 노드 개수 max_distance = 0 # 도달 가능한 노드중, 가장 멀리 있는 노드와의 최단거리 for d in distance: if d != 1e9: #도달 가능 count += 1 max_distance = max(max_distance, d) print(count - 1, max_distance)
문제2) 미래도시
수행과정
- n개 회사 ,m개 간선 ( 양방향, 비용 = 1) ( n,m ≤ 100 )
- 1번회사 → k → x번 회사로 이동 : 최소시간 구하기
idea
- 플로이드
INF = int(1e9) n , m = int(input().split()) # 노드, 간선 수 graph = [[INF]*(n+1) for _ in range(n+1) ] #자기 자신으로 이동하는 비용은 0 for a in range(1,n+1): for b in range(1,n+1): if a==b: graph[a][b] = 0 # 간선에 대한 정보를 입력 받아 , 그 값으로 초기화 for _ in range(m): a,b = map(int,input().split()) graph[a][b] = 1 # a<->b 비용은 1 graph[b][a] = 1 x,k = map(int,input().split()) # 점화식 for k in range(1,n+1): for a in range(1,n+1): for b in range(1, n+1): graph[a][b] = min(graph[a][b], graph[a][k]+graph[k][b]) #결과 for a in range(1,n+1); for b in range(1,n+1): #도달 못한 경우 if graph[a][b] == INF: print("도달못함") else: print(graph[a][b**])**
'알고리즘' 카테고리의 다른 글
[알고리즘] 유명 알고리즘 대회 (0) 2022.09.26 [알고리즘] M 기업 코딩테스트 (0) 2022.09.26 [알고리즘] 이진 탐색 정리 (1) 2022.09.16 [알고리즘] 정렬 정리 (1) 2022.09.16 [알고리즘] 구현 정리 (0) 2022.09.16