최단 경로 알고리즘

최단 경로 알고리즘❓

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

• 한 지점에서 다른 한 지점까지의 최단 경로
• 한 지점에서 다른 모든 지점까지의 최단 경로 - 다익스트라
• 모든 지점에서 다른 모든 지점까지의 최단 경로 - 플로이드 워셜

---

다익스트라 알고리즘

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

• 음의 간선이 없을 때 정상 동작
• 그리디 알고리즘으로 분류 (매 상황에서 가장 비용이 적은 노드를 선택)

동작 과정

1. 출발 노드를 설정
2. 최단 거리 테이블을 초기화
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신
5. 3번과 4번을 반복

코드 (선형 탐색)

: 최단 거리가 가장 짧은 노드를 매번 선형 탐색해야 함
시간 복잡도 : O(V2)

n = 6 # 노드의 개수

graph = [[] for i in range(n + 1)]
visited = [False] * (n + 1)
INF = int(1e9)
distance = [INF] * (n + 1)

graph = [[], [(2, 2), (3, 5), (4, 1)], [(3, 3), (4, 2)], [(2, 3), (6, 5)],
         [(3, 3), (5, 1)], [(3, 1), (6, 2)], []]


def dijkstra(start):
  # 시작 노드에 대해서 초기화
  distance[start] = 0
  visited[start] = True
  for adj in graph[start]:
    distance[adj[0]] = adj[1]

  # 시작 노드 제외 노드에 대해 반복
  for i in range(n-1):
    now = get_smallest_node()
    visited[now] = True
    for adj in graph[now]:
      cost = distance[now] + adj[1]
      # 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경
      if cost < distance[adj[0]]:
        distance[adj[0]] = cost

# 방문하지 않은 노드 중 가장 최단 거리가 짧은 노드 번호 반환
def get_smallest_node():
  min_value = INF
  index = -1
  for i in range(1, n+1):
    if distance[i] < min_value and not visited[i]:
      min_value = distance[i]
      index = i
  return index

# 시작 노드 번호
start = 1
dijkstra(start)

for i in range(1, n+1):
  # 도달할 수 없는 경우
  if distance[i] == INF:
    print(f'{start} -> {i}: 도달할 수 없습니다')
  else: print(f'{start} -> {i} : {distance[i]}')

개선된 코드 (우선순위 큐)

import heapq

n = 6 # 노드의 개수

graph = [[],
         [(2, 2), (3, 5), (4, 1)],
         [(3, 3), (4, 2)],
         [(2, 3), (6, 5)],
         [(3, 3), (5, 1)],
         [(3, 1), (6, 2)],
         []]
start = 1 # 시작 노드 번호
INF = int(1e9)
distance = [INF] * (n + 1)

q = []

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

while q: # 큐가 비어있지 않다면
  # 가장 최단 거리가 짧은 노드 정보
  now_dist, now = heapq.heappop(q)
  # 현재 노드가 이미 처리된 적이 있는 노드라면 무시
  # 테이블 거리 < 큐에 있던 거리(옛날 거)
  if distance[now] < now_dist:
    continue
  for next_node, weight in graph[now]:
    cost = now_dist + weight
    if cost < distance[next_node]:
      distance[next_node] = cost
      heapq.heappush(q, (cost, next_node))

for i in range(1, n+1):
  # 도달할 수 없는 경우
  if distance[i] == INF:
    print(f'{start} -> {i}: 도달할 수 없습니다')
  else: print(f'{start} -> {i} : {distance[i]}')

---

플로이드 워셜 알고리즘

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

• 거쳐 가는 노드를 기준으로 알고리즘 수행
• 최단 거리를 갖는 노드 찾는 과정 필요 X
• 다이나믹 프로그래밍으로 분류
  • 특정한 노드 k를 거쳐 가는 경우를 확인
  • a에서 b로 가는 최단 거리보다 a에서 k를 거쳐 b로 가는 거리가 더 짧은지 검사
  • 점화식: Dab = min(Dab, Dak + Dkb)

코드

n = 4 # 노드 개수
INF = int(1e9)

graph = [[], [(2, 4), (4, 6)], [(1, 3), (3, 7)], [(1, 5), (4, 4)], [(3, 2)]]
# 2차원 테이블에 최단 거리 정보 저장
d = [[INF] * (n+1) for _ in range(n+1)]

for node in range(1, n+1):
  d[node][node] = 0
  for adj, cost in graph[node]:
    d[node][adj] = cost
    
for k in range(1, n+1): # k번 노드를 거쳐 가는 경우
  for a in range(1, n+1):
    if a == k: continue
    for b in range(1, n+1):
        if b == k: continue
        d[a][b] = min(d[a][b], d[a][k] + d[k][b])

# 결과 출력
for a in range(1, n+1):
  for b in range(1, n+1):
    if d[a][b] == INF:
      print(f'{a} -> {b} : 도달할 수 없음')
    else:
      print(f'{a} -> {b} : {d[a][b]}')