최단 경로

1. 다익스트라 알고리즘

- 특정 노드 -> 다른 모든 노드를 가는 최단 경로를 구함

- '음의 간선'이 없을 때 사용 가능 (GPS SW  기본 알고리즘으로 사용)

- 그리디 알고리즘

- 출발 노드를 설정한 후, 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택해가는 알고리즘

- 입력 시 sys.std.realine()으로 사용하는 것 추천!

- 헷갈리지 말 것 : dist를 갱신하는 거랑 노드를 선택하는 과정을 별개로 생각하기! 

 

* 간단하지만 오래 걸리는 구현 방식

#DFS로 구현 
#리스트 : 노드 개수 + 1

import sys
input = sys.stdin.readline
INF = int(le9) #무한대.10억


#입력받기
N,M = map(int,input().split() #노드개수,간선개수
start = int(input()) #시작 노드 번호
graph = [ [] for i in range(N+1) ] #각 노드에 연결되어 있는 노드 정보 리스트
visited = [False] * (N+1) #방문 리스트
distance = [INF] * (N+1) #최단 거리 테이블


#모든 간선 정보 입력받기
for _ in range(M):
  a,b,c = map(int,input().split()) #a -> b노드로 갈 때 c 비용
  graph[a].append((b,c))


#방문하지 않은 노드 중, 최단 거리가 가장 짧은 노드 번호 반환하는 함수
def get_smallest_node():
  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


def dijkstra(start):
   #시작 노드의 그래프  초기화
   distance[start] = 0
   visited[start] = 0

  #시작 노드와 연결된 노드에 대한 distance값 입력(node[0] : 노드index, node[1]:간선)
   for node in graph[start]:
       distance[node[0]] = node[1] 
   for i in range(N - 1) : #시작 노드 제외 N-1개 노드에 대해 반복
      #현재 노드 선택 
      cur = get_smallest_node()
      visited[cur] = True
      
      #현재 노드와 연결된 다른 노드들 확인
      for j in graph[cur]:
         cost = distance[cur] + j[1]

      #현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우 distance 갱신
         if cost < distance[j[0]]:
               distance[j[0]] = cost
               
 #알고리즘 수행              
 dijkstra(start)
 
 #모든 노드로 가기 위한 최다 ㄴ거리 출력
 for i in range(1,N+1):
 	if distnace[i] == INF:
    	print("INFINITY")
    else:
    	print(distance[i])

- O(V^2)

- 노드 개수가 5000개 이하일 때 가능

 

*개선된 알고리즘

- O(ElogV) : V는 노드 개수, E는 간선 개수

- heap(우선순위 큐) 사용

- python에서는 표준 라이브러리로 PriorityQueue와 heapq를 제공. 보통 heapq가 좀 더 빠름

- 최단 거리가 가장 짧은 노드를 선택하는 함수를 우선순위 큐로 구할 수 있다.

#우선순위 큐 사용 
import heapq
import sys
input = sys.stdin.readline
INF = int(le9)

#입력받기
N,M = map(int,input().split() #노드개수,간선개수
start = int(input()) #시작 노드 번호
graph = [ [] for i in range(N+1) ] #각 노드에 연결되어 있는 노드 정보 리스트
visited = [False] * (N+1) #방문 리스트
distance = [INF] * (N+1) #최단 거리 테이블

#모든 간선 정보 입력받기
for _ in range(M):
  a,b,c = map(int,input().split()) #a -> b노드로 갈 때 c 비용
  graph[a].append((b,c))

def dijkstra(start):
  q = []   # (해당 노드까지 최단경로,노드) 입력 

  #시작노드를 큐에 삽입
  heapq.heappush(q,(0,start))
  distance[start] = 0
  while q: 

    #가장 최단 거리가 짧은 노드 정보 가져오기
    dist, cur_node = heapq.heqppop(q)
    
    # 이미 그 노드로 가는 최단 경로를 구한 적 있고, 그 거리가 큐에서 뽑은 거리보다 작은 경우 
    if distance[cur_node] < dist:
      continue
      
   # 아직 최단 경로를 구한 적 없거나, 에전에 거리를 구했어도 지금 큐에서 뽑은 거리가 더 작은 경우 
   else:
      for adj_node in graph[cur_node]: #해당 노드에 연결된 인접 노드 확인. adj_node[0] : 인접 노드 번호, adj_node[1] : cur_node - 인접 노드 까지의 거리  
        cost = dist + adj_node[1]  
        if cost < distance[adj_node[0]]:
           distance[adj_node[0]] = cost 
           heapq.heqppush(q, (cost, adj_node[0]))

dikstra(start)

        

 

2. 플로이드 워셜 알고리즘 

- 모든 지점에서 다른 모든 지점까지의 최단 경로를 구하는 경우 사용

- 음의 간선이  없음을 가정

- O(N^3)

- 2차원 리스트에 최단 거리 정보 저장

-  DISab : a를 거쳐 b로 가는 최단 거리

DISab = min(DISab, DISak + DISkb)

#플로이드 워셜 알고리즘

N, M = map(int,input().split()) #노드 개수, 간선 개수
graph = [[INF] * (N+1) for _ in range(N+1)] #2차원 리스트. 노드-> 노드로 가는 최단 경로

#자기 자신으로 가는 비용은 0으로 초기화
for a in range(1, N+1):
	for b in range(1, N+1):
    	if a == b:
        	graph[a][b] = 0

#a노드 -> b노드로 가는 간선 정보 입력받기
for _ in range(M):
	a,b,c = map(int,input().split())
    graph[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("INFINITY", end = " ")
         else:
         	print(graph[a][b], end = " ")
    print()

 

3. 벨만 포드 알고리즘 

- 한 지점에서 다른 모든 지점까지의 최단 경로를 구하는 경우 사용

- 음의 간선이 있는 경우 사용 가능 

- 현재 간선을 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우, 거리 정보 갱신

- n-1번 반복 이후, n번째 반복에서도 거리 값이 갱신된다면 음수 순환이 존재

- 다익스트라와의 차이점:  매 반복마다 모든 간선을 확인한다는 것( 다익스트라는 방문하지 않는 노드 중에서 최단 거리가 가장 가까운 노드만을 방문)

 

import sys
input = sys.stdin.readline
INF = int(1e9)

if __name__ == "__main__":
	N, M = map(int,input().split()) #N은 노드, M은 간선 
	bus = [] #모든 간선 정보 
	dist = [INF] * (N+1) #최단 거리 테이블 

	#A -> B까지 C의 비용이 든다. 
	for _ in range(M):
		a,b,c = map(int,input().split())
		bus.append((a,b,c))

	#벨만포드 알고리즘 
	def bell(start):
		dist[start] = 0 #시작노드는 항상 거리 0
		for i in range(N):  
			for j in range(M): #모든 간선에 대해 탐색 
				cur_n = bus[j][0] 
				next_n = bus[j][1] 
				cost = bus[j][2]
				#현재 간선을 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우 update
				if dist[cur_n] != INF and dist[next_n] > dist[cur_n] + cost:
					dist[next_n] = dist[cur_n] + cost
					#N-1번 이후 반복에도 값이 갱신되는 경우, 음수 loop
					if i == N-1:
						return True
		return False
	
	#벨만포드 수행
	is_negative_cycle = bell(1)
	if is_negative_cycle:
		print('-1') 
	else:
		#1번 노드를 제외한 다른 모든 노드로 가기위한 최단 거리
		for i in range(2,N+1):
			if dist[i] == INF:
				print('-1')
			else:
				print(dist[i])

3. 예제

1) 판매원 문제

-  1번 회사에서 출발하여 K번 회사를 거쳐 X번 회사로 가는 방법 중 가장 최단 시간을 출력

( 회사의 개수 = N, 경로 개수 = M, 만약 X번 회사로 갈 수 없으면 -1 출력 )

-  "경유지"가 있는 경우, A - K, K - X 각각의 최단 경로를 구해야 하므로 플로이드 워셜 알고리즘 수행

- 자기 자신으로 가는 비용은 0, 인접한(경로가 있는) 도시끼리는 1로 비용 초기화 후, 알고리즘 수행

 

2)  전보

- 특정 C 도시에서 최대한 많은 도시들에게 전보를 퍼트리고 싶을 때, 메세지를 받게 되는 최대 도시 개수와 도시들이 모두 메세지를 받는데 까지 걸리는 시간은 얼마인지 출력

- 한 도시에서 다른 도시까지의 최단 거리를 구해야 한다는 점에서 다익스트라 알고리즘이 적합

- BFS이 부적합한 이유 : BFS로 최단 경로를 구하는 경우는 간선의 비용이 모두 똑같을 때만 사용 가능. 만약 이 문제처럼 노드 간 비용이 다르면 다익스트라 쓰기!

 

3) 타임머신

- 1번 도시에서 다른 모든 도시까지 가는 최단 시간을 출력

- 단 음의 시간이 존재할 수 있다.

- 음의 간선이 존재하는 경우, 벨만 포드 알고리즘