[알고리즘] 8. 최단 경로 알고리즘

Index

1. 최단 경로 문제

2. 다익스트라 최단 경로

3. 플로이드 워셜

4. 벨만 포드

5. 추천 문제

6. 참고자료

---

1. 최단 경로 문제

최단 경로 문제

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

- 각 지점은 그래프에서 node로 표현, 지점 간 연결된 도로는 edge로 표현

 

(최단 경로 유형)

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

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

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

 

2.  다익스트라 최단 경로

Djikstra

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

- 음의 간선이 없을 때 정상적으로 동작

- 매 상황에서 방문하지 않은 가장 적은 비용이 드는 노드를 선택(그리디)

- 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾음

- 테이블에 각 노드까지의 최단 거리 정보가 저장

 

(동작 과정)

1) 출발 노드를 설정

2) 최단 거리 테이블을 초기화

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

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

5) 위 과정에서 3번과 4번은 반복

 

- O(V)번에 걸쳐 최단 거리가 가장 짧은 노드를 매번 선형 탐색, O(V^2)

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

n, m = map(int, input().split())
start = init(input())
graph = [[] for i in range(n+1)]
visited = [False] * (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
  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):     
    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[i] == INF:
    if distance[i] == INF:
      print("INF")
    else:
      print(distance[i])

 

Priority Queue

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

- Min Heap / Max Heap

- 삽입 삭제에 O(logN)

import heapq

def heapsort(arr):
  h = []
  result = []
  for value in arr:
    heapq.heappush(h, value)
  for i in range(len(h)):
    result.append(heapq.heappop(h))
  return result

 

(개선된 구현)

- 단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 Min Heap을 사용

- O(ElogV)

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

n, m = map(int, input().split())
start = init(input())
graph = [[] for i in range(n+1)]
visited = [False] * (n+1)

# 간선 정보
for _ in range(m):
  a, b, c = map(int, input().split())
  graph[a].append((b,c))
  
   
def dijkstra(start):
  q = []
 
dijkstra(start)

for i in range(1, n+1):
  if distance[i] == INF:
    if distance[i] == INF:
      print("INF")
    else:
      print(distance[i])

 

3.  플로이드 워셜

플로이드 워셜(Floyd-Warshell)

- 2차원 테이블 이용하여 최단거리 정보 저장

- DP 알고리즘(3중 반복)

- 점화식: D_ab = min(D_ab, D_ak + D_kb), 각 당계마다 특정노드 K를 거쳐가는 경우를 확인

 

 

4.  벨만 포드

 

5. 추천 문제

다익스트라

- 등산코스 정하기(https://school.programmers.co.kr/learn/courses/30/lessons/118669)

- 배달(https://school.programmers.co.kr/learn/courses/30/lessons/12978)

- 합승 택시 요금(https://school.programmers.co.kr/learn/courses/30/lessons/72413)

- 가장 먼 노드(https://school.programmers.co.kr/learn/courses/30/lessons/49189)

 

플로이드 워셜

- 순위(https://school.programmers.co.kr/learn/courses/30/lessons/49191)

- 플로이드(https://www.acmicpc.net/problem/11404)

- 맥주 마시면서 걸어가기(https://www.acmicpc.net/problem/9205)

 

벨만 포드

- 

- 

 

---

참고 자료

[Video: 동빈나의 이코테 2021(최단 경로 알고리즘)] https://www.youtube.com/watch?v=acqm9mM1P6o&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=7

[Video: 동빈나의 이코테 2021(벨만 포드 알고리즘)] https://www.youtube.com/watch?v=Ppimbaxm8d8&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=13