[알고리즘 개념] 최단 경로 알고리즘

1. 최단 경로 알고리즘이란?

- 가장 짧은 경로를 찾는 알고리즘

- 다양한 문제 상황

① 한 지점에서 다른 한 지점까지의 최단 경로

② 한 지점에서 다른 모든 지점까지의 최단 경로

③ 모든 지점에서 다른 모든 지점까지의 최단 경로

- 각 지점은 그래프에서 노드로 표현

- 지점 간 연결된 도로는 그래프에서 간선으로 표현

- 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 꼐산

- 다익스라 최단 경로 알고리즘은 음의 간선이 없을 때 정상 동작

- 다익스트라 최단 경로 알고리즘은 매 상황에서 가장 비용이 적은 노드를 선택하기에 그리디 알고리즘으로 분류

- 동작과정은 다음과 같다

① 출발 노드를 설정

② 최단 거리 테이블 초기롸

③ 방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드 선택

④ 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 태이블 갱신

⑤ 위 과정에서 3번과 4번을 반복

 

○ 다익스트라 알고리즘

import sys

input = sys.stdin.readline
INF = 1e9  # 무한을 의미하는 값으로 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 i in range(m):
  a, b, c = map(int, input().split())
  graph[a].append((b, c))

# 방문하지 않은 노드 중에서, 가장 최단 거리가 짧은 노드의 번호를 반환
def getSmallestNode():
  minVal = INF
  index = 0  # 가장 최단 거리가 짧은 노드(인덱스)
  for i in range(1, n + 1):
    if distance[i] < minVal and not visited[i]:
      minVal = distance[i]
      index = 1
  return index

def dijkstra(start):
  # 시작 노드에 대해서 초기화
  distance[start] = 0
  visited[start] = True
  for g in graph[start]:
    distance[g[0]] = g[1]
  # 시작 노드를 제외한 전체 n-1개의 노드에 대해 반복
  for i in range(n - 1):
    # 현재 최단 거리가 가장 짧은 노드를 꺼내서, 방문 처리
    now = getSmallestNode()
    graph[now] = True
    # 현재 노드와 연결된 다른 노드를 확인
    for j in graph[now]:
      cost = distance[now] + [1]
      # 현재 노드를 거쳐 다른 노드로 이동하느 거리가 더 짧은 경우
      if cost > distance[j[0]]:
        distance[j[0]] = cost
        
# 다익스트라 알고리즘 수행
dijkstra(start)

# 모든 노드로 가기 위한 최단 거리 출력
for _ in range(1, n + 1):
  # 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
  if distance[i] == INF:
    print("INFINITY")
  # 도달할 수 있는 경우 거리를 출력
  else:
    print(distance[i])

 

2. 우선순위 큐(Priority Queue)란?

- 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조

 

3. 힙(Heap)이란?

- 우선순위 큐를 구현하기 위해 사용하는 자료구조 중 하나

- 최소 힙과 최대 힙이 있다.

 

○ 힙

import heapq

# 오름차순 힙 정렬(Heap Sort)
def heapsort(iterable):
  h = []
  result = []
  # 모든 원소를 차례대로 힙에 삽입
  for value in iterable:
    heapq.heappush(h, value)
  # 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
  for i in range(len(h)):
    result.append(heapq.heappop(h))
  return result
result = heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
print(result)

 

출력

[0,1,2,3,4,5,6,7,8,9]

 

 

 

- 방문하지 않은 노드 중 최단거리가 가장 짧은 노드를 선택하기 위해 힙 자료구조를 이용

 

○ 개선된 다익스트라 알고리즘

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 i in range(m):
  a, b, c = map(int, input().split())
  graph[a].append((b, c))


def dijstra(start):
  q = []
  # 시작 노드로 가기 위한 최단경로는 0으로 설정하여 큐에 삽입
  heapq.heappush(q, (0, start))
  distance[start] = 0
  while q: # 큐가 비어있지 않다면
    # 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
    dist, now = heapq.heqppop(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]))


# 다익스트라 알고리즘 수행
dijstra(start)

# 모든 노드로 가기위한 최단거리를 출력
for i in range(1, n + 1):
  if distance[i] == INF:
    print("INFINTY")
  else:
    print(distance[i])

- 힙 자료구조를 이용하는 알고리즘의 시간 복잡도는 O입니다.

 

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

- 모든 노드에서 다른 모든 노드까지의 최단경로를 모두 계산한다.

- 다익스트라와 마찬가지로 단계별로 거쳐가는 노드를 기준으로 알고리즘을 수행하지만 방문하지 않는 노드 중 최단거리를 찾는 노드를 찾는 과정이 필요하지 않다.

- 2차원 테이블에 최단거리 정보를 저장한다.

- 점화식 : D(ab) = min(D(ab),D(ak)+D(kb))

 

○ 플로이드 워셜 알고리즘

import sys

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

n = int(input())
m = int(input())
# 노드간 거리를 2차원 리스트로 만들고, 모두 초기화 
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
# graph에 노드간 거리 입력받음
for _ in range(m):
  a, b, c = map(int, input().split())
  # a에서 b로 가는 비용은 c
  graph[a][b] = c
# 점화식에 따라 플로이드 워셜 알고리즘을 수행
for k in range(1, n+1):
  for i in range(1, n+1):
    for j in range(1, n+1):
      graph[i][j] = min(graph[i][j],graph[i][k] + graph[k][j])
# 수행된 결과를 출력
for i in range(1,n+1):
  for j in range(1,n+1):
    # 도달하지 않는 경우
    if INF == graph[i][j]:
      print("INFINITY", end = " ")
    # 도달할 수 있는 경우
    else:
      print(graph[i][j], end=" ")

 

# 연습문제

[1] 전보

어떤 나라에는 N개의 도시가 있다. 각 도시는 보내고자 하는 메시지가 있는 경우, 다른 도시로 전보를 보내서 다른 도시로 해당 메시지를 전송할 수 있다. 각 도시의 번호와 통로가 설치되어 있는 정보가 주어졌을 때, 한 도시에서 보낸 메시지가 최대한 많이 퍼지도록 할때 메시지를 받게 되는 도시는 총 몇 개이며 도시들이 모두 메시지를 받는 데까지 걸리는 시간은 얼마인지 계산한는 프로그램을 작성하시오.

import sys
import heapq

input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정
# 노드와 개수, 간선의 개수, 시작 노드를 입력 받기
n,m,start = map(int, input().split())
# 각 노드와 연결되어 있는 노드에 대한
graph = [[] for i in range(n + 1)]
distance = [INF] * (n+1)

for i in range(m):
  x,y,z = map(int, input().split())
  graph[x].append((y,z))
  
def dijkstra(start):
  q = []
  # 시작 노드로 가기 위한 최단 거리는 0으로 설정하며, 큐에 삽입
  heapq.heappush(q,(0, start))
  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.heappush(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)
    
# 시작 노드는 제외하므로 count-1 출력
print(count-1, max_distance)

 

입력

3 2 1
1 2 4
1 3 2

 

 

출력

2 4

 

[2] 미래 도시

미래도시에는 1번부터 N번까지의 회사가 있는데 특정회사끼리는 도로를 통해 연결되어 있고 양방향으로 이동할 수 있으며 정확히 1만큼의 시간으로 이동할 수 있다. 방문 판매원은 1번 회사에서 출발하면 K번 회사를 방문한 뒤 X번 회사로 가는것이 목표이다. 이동 최소시간을 구하여라.

- 첫째 줄에 전체 회사의 개수 N과 경로의 개수 M이 공백으로 구분되어 차례대로 주어진다.

- 둘째 줄부터 M+1번째 줄에는 연걸된 두 회사의 번호가 공백으로 주어진다.

- M+2번째 줄에는 X와 K가 공백으로 구분되어 차례대로 주어진다.

import sys

input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정
# 노드와 개수, 간선의 개수, 시작 노드를 입력 받기
n,m = map(int, input().split())
# 2차원 리스트를 만글고, 모든 값을 무한으로 초기화
graph = [[INF]*(n+1) for _ in range(n+1)]

# 자기자신으로 가는 비용은 0으로 초기화
for i in range(1,n+1):
  for j in range(1,n+1):
    if i == j:
      graph[i][j] = 0
# 각 간선에 대한 정보를 입력 받아, 그 값으로 초기화
for _ in range(m):
  # A와 B가 서로에게 가는 비용은 1이라고 설정
  a,b = map(int, input().split())
  graph[a][b] = 1
  graph[b][a] = 1
  
x,k = map(int, input().split())

# 점화식에 따라 플로이드 위셜 알고리즘 수행
for k in range(1,n+1):
  for i in range(1,n+1):
    for j in range(1,n+1):
      graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

# 수행된 결과 출력
result = graph[1][k] + graph[k][x]

# 도달할 수 없는 경우, -1을 출력
if result == INF:
  print("-1")
# 도달할 수 있다면, 최단 거리를 출력
else:
  print(result)

 

입력

5 7
1 2
1 3
1 4
2 4
3 4
3 5
4 5
4 5

 

 

출력

3