최단 경로 찾기 알고리즘 (다익스트라, 벨만포드, 플로이드 워셜), 관련 백준 문제 파이썬 풀이

3가지 최단 경로 찾기 알고리즘과 각각이 어떤 문제에서 사용되는지에 대한 포스팅입니다 .

1️⃣ 다익스트라(dijkstra) : 대부분의 최단 경로 문제

다익스트라는 최단 경로 찾기 알고리즘 중 가장 빠르기 때문에 대부분의 문제에서 사용합니다. (다익스트라의 시간복잡도는 O(N+ElogE)입니다. 

💛 다익스트라 전체 코드 (백준 1753)

import heapq

V, E = map(int, input().split())
K = int(input())
adjList = [[] for _ in range(V+1)]
for i in range(E):
    u, v, w = map(int, input().split())
    adjList[u].append((v,w))

hq = []
visited = [0]*(V+1)
heapq.heappush(hq, (0, K))
dist = [float('inf')]*(V+1) # 도착점 i에 대한 최단 경로
dist[K] = 0
while hq:
    distance, temp = heapq.heappop(hq)
    if visited[temp]: continue
    visited[temp] = 1
    for to, cost in adjList[temp]:
        if distance+cost < dist[to]:
            dist[to] = distance+cost
            heapq.heappush(hq, [distance+cost, to])

for i in range(1, V+1):
    if dist[i] == float('inf'):
        print('INF')
    else:
        print(dist[i])

 

💚 다익스트라 관련 백준 문제 

1753번: 최단경로

5719번: 거의 최단 경로

1753번: 최단경로

 

 

2️⃣ 벨만포드(bellmanFord) : 간선 비용 중 음수가 있을 때

💚 벨만포드 관련 문제

11657번: 타임머신

11657번: 타임머신

 

3️⃣ 플로이드 워셜(Floyd-Warshall)

• 플로이드 워셜은 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘 입니다. (코드 이해가 쉬움)
• 플로이드 워셜로 풀이할 수 있는 문제는 모두 다익스트라로 풀 수 있기 때문에 저는 더 빠른 다익스트라를 선호합니다.
• i > k이고 k > j 이면 i > j를 만족함을 이용합니다. 
• s부터 e까지 가는 최단 거리를 d[s][e]라고 정의할 때, d에 대한 구현은  d[s][e] = min(d[s][e], d[s][m] + d[m][e])

for m in range(1, N+1):
	  for s in range(1, N+1):
		    for e in range(1, N+1):
			      d[s][e] = min(d[s][e], d[s][m] + d[m][e])

 

💚 플로이드 워셜 관련 문제

2458번: 키 순서