[알고리즘] 최단경로 정리

최단경로 - 가장짧은 경로 찾기

• 다이나믹도 가능하다
• 그래프에서 각 지점을 노드와 간선으로 표시
• 문제상황
  • 한지점에서 다른 지점까지 경로
  • 한지점에서 다른 모든 지점까지의 경로
  • 모든 지점에서 다른 모든 지점까지의 경로

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**])**