🚗 최단 경로

🚗 최단 경로

• 가장 짧은 경로를 찾는 알고리즘으로 그래프를 이용해 표현

🚗 간단한 다익스트라 최단 경로알고리즘

• 여러개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘
• 그리디 알고리즘
• 다익스트라 알고리즘 시간 복잡도 : O(V^2)

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

n, m = map(int, input().split()) # n, m 노드의 개수와 간선의 개수 입력
start = int(input()) # 시작노드 입력

graph = [[] for i in range(n+1)] # 노드개수 + 1개의 그래프 만들기(0은 비워주고 1부터 6까지 즉 7개 생성)
visited = [False]*(n+1) # 노드에 방문했는지 확인하기 위한 배열 마찬가지로 n+1개 생성
distance = [INF]*(n+1) # 거리 또한 n+1개 생성 inf로 초기화

# 간선의 개수만큼 반복해서 모든 간선 정보 입력받기
for _ in range(m):
  a, b, c = map(int, input().split())
  graph[a].append((b,c)) # 총 n개의 노드에 각각 정보 추가

# 방문하지 않은 노드 중에서, 가장 최단 거리가 짧은 노드의 번호 반환
def get_smallest_node():
  min_value = INF
  index = 0 # 가장 거리 짧은 노드
  for i in range(1, n+1):
    # 만약 i번 노드가 min_value보다 작고, 방문되지 않앗다면
    if distance[i] < min_value and not visited[i]:
      min_value = distance[i] # min_value 값 업데이트
      index = i
  print(index)
  return index

# 다익스트라 알고리즘 구현 -> 시작노드를 매개변수로 입력받음
def dijkstra(start):
  distance[start] = 0 # 시작노드의 거리 0으로 초기화
  visited[start] = True # 들어온 시작노드 방문처리
  # 지금 노드로 가서 노드의 거리 정보를 distance 배열에 담음
  for j in graph[start]:
    distance[j[0]] = j[1] # 목적지 노드 j[0], 거리 j[1]
  # 방문 시작
  for i in range(n-1):
    now = get_smallest_node() # 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:
    print("infinity")
  else:
    print(distance[i])

🚗 개선된 다익스트라 알고리즘

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

# 노드 간선 개수, 시작 노드 입력 받기
n, m = map(int, input().split())
start = int(input())

graph = [[] for i in range(n+1)] # 각 노드의 연결정보가 담겨있는 리스트
distance = [INF]*(n+1) # 최단 거리 테이블 무한으로 초기화

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

def dijkstra(start):
  q = []
  heapq.heappush([], (0, start))
  distance[start] = 0
  print(type(q))
  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("INF")
  else:
    print(distance)

🚗 플로이드 워셜 알고리즘

• 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우
• DP 알고리즘
• 플로이드 워셜의 시간 복잡도 : O(N$^3$)

INF = int(1e9)

n = int(input())
m = int(input())

# 정보를 담을 2차원 리스트 초기화
graph = [[INF] * (n+1) for _ in range(n+1)]

# 자기 자신 -> 자기자신 비용 0으로 초기화
for i in range(1, n+1):
  for j in range(1, n+1):
    if i == j:
      graph[i][j] = 0

# 간선 정보 입력
for _ in range(m):
  a, b, c = map(int, input().split())
  graph[a][b] = c

for k in range(1, n+1): # 현재 거쳐 가는 노드
  for i in range(1, n+1): # 출발 정점
    for j in range(1, n+1): # 도착 정점
      graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

for i in range(1, n+1):
  for j in range(1, n+1):
    if graph[i][j] == INF:
      print("INF")
    else:
      print(graph[i][j], end=' ')
  print()