[알고리즘] 다익스트라 최단거리 알고리즘

O(V^2). V=노드의 개수. V가 5000이하면 사용할만하다. 그 이상 되면 우선순위 큐 사용.

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

n, m = map(int, input().split)
start = int(input())
graph = [ [] for i in range(n+1)]
visited = [False]*(n+1)
distance = [INF]*(n+1)


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

def get_smallest_node():
  min_value = INF
  index = 0
  for i in range(1,n+1):
    if distance[i]<min_value and not visited[i]:
      min_value = distance[i]
      index = i
  return index

def dijkstra(start):
  distance[start] = 0
  visited[start]=True
  for j in graph[start]:
    distance[j[0]]=j[1]
  for i in range(n-1):
    now = 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])

 

 

우선순위 큐(heapq)를 사용한 향상된 알고리즘-> O(ElogV)

: 가장 작은 값을 찾기 위해 사용하던 함수(get_smallest_node())를 사용하지 않게끔 heapq를 사용하여 복잡도를 줄인다.

heapq의 삽입/삭제 모두 O(logN). 힙정렬:O(NlogN).

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(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])

 

문제 - 전보

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

n,m,start = map(int,input().split())
graph=[ [] for i in range(n+1)]
distance=[INF]*(n+1)

for _ in range(m):
  x, y, z = map(int,input().split())
  graph[x].append((y,z))

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] #현재 노드를 거쳐서 다른 노드로 이동하는 cost
      if cost<distance[i[0]]: #cost가 기존에 저장된 거리보다 작은 경우
        distance[i[0]]=cost #바꾸기
        heapq.heappush(q,(cost,i[0])) #그 cost와 노드를 heap에 추가

dijkstra(start)

count = 0
max_distance =0
for d in distance:
  if d<INF:
    count+=1
    max_distance=max(d,max_distance)

print((count-1),max_distance)