[알고리즘] 최단경로(다익스트라, 플로이드워셜, 벨만포드)

1. 다익스트라 알고리즘 O(ElogV)

• 한 지점에서 다른 특정 지점까지의 최단 경로를 구할 때 사용
• 음의 경로가 있으면 사용할 수 없음(=가중치가 양수일 때만 사용 가능)
• heap(우선순위 큐)를 이용함으로써 시간복잡도를 줄일 수 있음

 

2. 다익스트라 알고리즘 코드

import heapq
INF = int(1e9)

n,m = map(int, input().split()) #n은 노드의 개수 m은 간선의 개수
start = int(input()) #출발점
graph = [[] for _ in range(n+1)]
distance = [INF] * (n+1)

for _ in range(m):
  a,b,c = map(int, input().split())
  graph[a].append((b,c)) #a노드에서 b노드로 가는 비용이 c임

def dijkstra(start):
  q = []
  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)

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

 

3. 다익스트라 관련 문제

- 1753 최단경로 O (골드4)

- 1504 특정한 최단 경로 O (골드4)

- 1446 지름길

- 1916 최소비용 구하기 O (골드5) 

- 5972 택배 배송 O (골드5)

- 14284 간선 이어가기 2

- 17396 백도어

- 1238 파티 O (골드3)

 

4. 플로이드 워셜 알고리즘 O(N^3)

• 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구할 수 있음
• 2차원 리스트를 이용
• a에서 b로 갈 때, a에서 k를 거쳐 b로 갈 때라는 두 개의 값을 비교해서 최솟값을 최단경로에 넣는 것

 

5. 플로이드 워셜 알고리즘 코드

INF = int(1e9)

n = int(input()) #노드
m = int(input()) #간선

graph = [[INF] * (n+1) for _ in range(n+1)]

for a in range(1,n+1): #자신의 노드와 자신의 노드의 거리는 0
  for b in range(1,n+1):
    if a==b:
      graph[a][b] = 0

for _ in range(m):
  a,b,c = map(int, input().split())
  graph[a][b] = c

for k in range(1,n+1):
  for a in range(1,n+1):
    for b in range(1,n+1):
      graph[a][b] = min(graph[a][b], graph[a][k]+graph[k][b])

for a in range(1,n+1):
  for b in range(1,n+1):
    if graph[a][b] == INF:
      print("INFINITY", end=" ")
    else:
      print(graph[a][b], end=" ")
  print()

 

6. 플로이드 워셜 관련 문제

- 11404 플로이드 O (골드4)

- 11403 경로찾기 O (실버1)

- 1389 케빈 베이컨의 6단계 법칙 O (실버1)

- 1956 운동 O (골드4)

- 14938 서강그라운드 O (골드4)

- 2458 키순서

- 10159 저울

 

7. 벨만포드 알고리즘 O(VE)

• 가중치가 음의 값이어도 동적하는 최단 경로 알고리즘
• 다익스트라보다 시간복잡도 측면에서 비효율적이기 때문에 가능하면 다익스트라 사용
• 음의 사이클이 존재하면 동작하지 않음(검토하는 과정이 필요함)

 

8. 다익스트라 알고리즘 vs 벨만포드 알고리즘

• 다익스트라 : 매번 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드 선택
• 벨만포드 : 매번 모든 간선을 전부 확인

 

9. 벨만포드 알고리즘 코드

INF = int(1e9)

n,m = map(int,input().split()) #n=정점 m=간선

edges = [] #간선의 정보 저장
dist = [INF] * (n+1) #최단거리 정보

for i in range(m):
  a,b,c = map(int, input().split())
  edges.append((a,b,c)) #간선의 정보 저장, a부터 b까지 c의 가중치가 듦

def bf(start):

  dist[start] = 0

  for i in range(n): #n번 round
    for j in range(m): #모든 간선 확인
      cur = edges[j][0]
      next_node = edges[j][1]
      cost = edges[j][2]

      if dist[cur] != INF and dist[next_node] > dist[cur] + cost:
        dist[next_node] = dist[cur] + cost

        if i == n-1: #음의 사이클 확인
          return True #음의 사이클이 있는 경우
  
  return False #음의 사이클이 없는 경우

cycle = bf(1)

if cycle: #음의 사이클이 있을 경우
  print(-1)

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

 

10. 벨만포드 알고리즘 관련 문제

- 11657 타임머신O (골드4)

- 1865 웜홀O (골드3)

- 7142 데이터 만들기3

- 1738 골목길