최단 경로 알고리즘

froajnzd·2024년 2월 3일

알고리즘 파이썬

algorithm

목록 보기

10/11

최단 경로 알고리즘
그래프 상에서 노드 간의 탐색 비용을 최소화하는 알고리즘이다

세 가지 최단 경로 알고리즘
1. 다익스트라
2. 벨만 포드
3. 플로이드 워셜

💡 최단 경로 알고리즘의 특징

1. 다익스트라

그리디하게 최소 비용 경로를 찾아간다
-> 출발 노드에서만 연결된 노드를 반복적으로 탐색하여 -> 다른 모든 노드까지의 최소 거리 비용을 구한다.

2. 벨만 포드

모든 경우의 수를 고려하는 동적 계획법이 사용된다
-> 매 단계마다 모든 간선을 전부 확인하여 -> 다른 노드까지의 최소 비용을 구한다.
모든 노드를 한 번씩 출발 노드로 만든다
음의 사이클 존재 여부 파악하고자 한다면, 마지막으로 1번 더 반복하여 총 V번 반복했을 때, V-1번의 결과와 값이 다르다면 음의 사이클이 있는 것이라 판별할 수 있다.

3. 플로이드 워셜

모든 노드간의 최단거리를 구하고, 이때 점화식을 사용한다. => 동적 계획법
점화식 : $D_{ij}$ = $min(D_{ij}, D_{ik} + D_{kj})$
각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인한다.
i->j와 i->k->j 경로 중 어느 것이 최소 비용인지를 찾는 것

3중 for문이 사용된다.

for k in range(1, V+1): 		# via
    graph[k][k] = 0				# 사이클이 없으므로 자기자신 = 0
    for i in range(1, V+1):		# src
        for j in range(1, V+1):	# dst
            graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j])

📕 문제의 조건

1. 다익스트라

가중 그래프에서
특정 한 노드에서 다른 노드까지의 최단거리를 구하고자 할 때
음의 간선이 없어야 한다.

2. 벨만 포드

가중 유향 그래프 상에서 (음의 가중치와 사이클이 존재)
특정 한 노드로부터 다른 노드까지의 최단 경로를 구하고자 할 때

3. 플로이드 워셜

모든 노드 간의 최단거리를 구하고자 할 때
(음의 가중치가 있더라도 사용할 수 있지만, 만약 음의 사이클이 있다면 벨만 포드를 사용해야 한다.)

🎡 시간 복잡도

다익스트라
$O((V+E)logV)$
벨만 포드
$O(VE)$
플로이드 워셜
$O(N^3)$

🔰 다익스트라 구현 방법

간단한 다익스트라

각 노드에 대한 최단 거리를 담는 1차원 리스트를 선언
단계마다 방문하지 않은 노드 중 최단거리가 가장 짧은 노드를 선택하기 위해, 1차원 리스트의 모든 원소를 순차 탐색한다
시간복잡도 : $O(V^2)$

개선된 다익스트라
힙 자료구조를 사용하는 우선순위 큐(Priority Queue)를 사용하여 특정 노드까지의 최단 거리에 대한 정보를 힙에 담아 처리한다.

def dijkstra(start) :
  q = [] # 큐가 사용할 공간
  heapq.heappush(q,(0,start))  # Start 데이터 push
  distance[start] = 0 # 최단경로테이블 최적해 갱신

  while q : # 큐가 비어질때까지 반복
    cost,node = heapq.heappop(q) #우선순위가 높은 데이터 POP ( 비용, 현재노드 )
    
    # 이미 방문한 노드인 경우 
    if distance[node] < cost : continue 

    for next in graph[node] :
      next_cost = next[1] + cost
      if next_cost < distance[next[0]] : 
        distance[next[0]] = next_cost #최단경로 테이블 최적해로 갱신
        heapq.heappush(q,(next_cost,next[0])) # 데이터 우선순위큐에 PUSH

시간복잡도: $O(E logV)$

🔰 벨만 포드 구현 방법

출발 노드 설정
최단 거리 테이블 초기화
다음 과정을 (V-1)번 반복
1. 모든 간선 E개를 하나씩 확인
2. 각 간선을 거쳐 다른 노드로 가는 비용을 계산해 최단거리테이블 갱신

def bellman_ford(start):
    # 시작 노드에 대해서 초기화
    distance[start] = 0
    # 전체 v - 1번의 라운드(round)를 반복
    for i in range(v):
        # 매 반복마다 '모든 간선'을 확인한다.
        for j in range(e):
            cur_node = edges[j][0]
            next_node = edges[j][1]
            edge_cost = edges[j][2]
            # 현재 간선을 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
            if distance[cur_node] != INF and distance[next_node] > distance[cur_node] + edge_cost:
                distance[next_node] = distance[cur_node] + edge_cost
                # v번째 라운드에서도 값이 갱신된다면 음수 순환이 존재
                if i == v - 1:
                    return True

🏃‍ 예시 문제 1 - 다익스트라

<BAEKJOON: 골드 4> 최단경로

해답

개선된 다익스트라 사용
PriorityQueue 사용 X -> 시간 초과
V*V의 2차원 그래프 -> 메모리 초과

import sys
from queue import PriorityQueue
inf = sys.maxsize
input = sys.stdin.readline
V, E = map(int, input().split())
K = int(input())
graph = [[] * (V+1) for _ in range(V+1)]
for _ in range(E):
    u, v, w = map(int, input().split())
    graph[u].append((v, w))
    # if graph[u][v] > w:
    #     graph[u][v] = w

dijstra = [inf] * (V+1)
dijstra[K] = 0

que = PriorityQueue()
que.put((0, K))
while not que.empty():
    weight, node = que.get()
    # 갱신
    if dijstra[node] < weight:
        continue
    # node와 연결된 다른 노드들을 큐에 삽입
    # for i in range(V):
    for next, edge in graph[node]:
        next_weight = weight + edge
        if dijstra[next] > next_weight:
            dijstra[next] = next_weight
            que.put((next_weight, next))

for i in range(1, V+1):
    if dijstra[i] == inf:
        print("INF")
    else:
        print(dijstra[i])

🏃‍ 예시 문제 2 - 벨만 포드

<BAEKJOON: 골드 4> 타임머신

해답

import sys
inf = sys.maxsize
input = sys.stdin.readline
N, M = map(int, input().split())
edges = []
for _ in range(M):
    a, b, c = map(int, input().split())
    edges.append((a, b, c))
dist = [inf]*(N+1)
dist[1] = 0

# N-1 번 반복
for i in range(N):
    # 모든 간선 확인
    for cur, next, cost in edges:
        if dist[cur] != inf and dist[cur] + cost < dist[next]:
            dist[next] = dist[cur]+cost
            # 만약 N 번째에 갱신이 있다면 음의 사이클이 있다는 것.
            if i == N-1:
                print(-1)
                exit(0)

for i in range(2, N+1):
    if dist[i] == inf:
        print(-1)
    else:
        print(dist[i])

🏃‍ 예시 문제 3 - 플로이드 워셜

<BAEKJOON: 골드 3> 역사

해답

💯 최단 경로 문제를 더 풀어보고 싶다면?

Hi I'm 열쯔엉

이전 포스트

분할 정복

다음 포스트

최단 경로 알고리즘

algorithm

💡 최단 경로 알고리즘의 특징

1. 다익스트라

2. 벨만 포드

3. 플로이드 워셜

📕 문제의 조건

1. 다익스트라

2. 벨만 포드

3. 플로이드 워셜

🎡 시간 복잡도

🔰 다익스트라 구현 방법

🔰 벨만 포드 구현 방법

🏃‍ 예시 문제 1 - 다익스트라

해답

🏃‍ 예시 문제 2 - 벨만 포드

해답

🏃‍ 예시 문제 3 - 플로이드 워셜

해답

💯 최단 경로 문제를 더 풀어보고 싶다면?

최단 경로 분류

다익스트라

벨만 포드

플로이드 워셜

분할 정복

크루스칼 알고리즘

0개의 댓글